Abstract.
We show that the region lit by a point light source inside a simple n -gon after at most k reflections off the boundary has combinatorial complexity O(n 2k ) , for any k≥ 1 . A lower bound of Ω ((n/k-Θ(1)) 2k ) is also established which matches the upper bound for any fixed k . A simple near-optimal algorithm for computing the illuminated region is presented, which runs in O(n 2k log n) time and O(n 2k ) space for k>1 , and in O(n 2 log 2 n) time and O(n 2 ) space for k=1 .
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received March 14, 1996, and in revised form December 22, 1997, and January 5, 1998.
Rights and permissions
About this article
Cite this article
Aronov, B., Davis, A., Dey, T. et al. Visibility with Multiple Reflections . Discrete Comput Geom 20, 61–78 (1998). https://doi.org/10.1007/PL00009378
Issue Date:
DOI: https://doi.org/10.1007/PL00009378