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.