The Complexity of Diffuse Reflections in a Simple Polygon
Date: September 25, 2006 at 1pm
Speaker: Albert Yu
The complexity of the visibility region formed by a point
light source after $k$ diffuse reflections in a simple $n$-sided polygon
is $O(n^9)$, which is the first result polynomial in $n$, with no
dependence on $k$. This bound is an exponential improvement over the
previous bound of $O(n^{2 \lceil (k+1)/2 \rceil +1})$ due to Prasad et
al. [1].
[1] D. Chithra Prasad, Sudebkumar Prasant Pal, and Tamal K. Dey.
Visibility with multiple diffuse reflections. Computational Geometry,
10(3):187-196, 1998.