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(n2k), 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(n2klog n) time and O(n2k) space for k ≥ 1, and in O(n2 log2 n) time and O(n2) space for k = 1.
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics