Visibility with Multiple Reflections |
| |
| Authors: | B. Aronov A. R. Davis T. K. Dey S. P. Pal D. C. Prasad |
| |
| Affiliation: | (1) Computer and Information Science Department, Polytechnic University, Brooklyn, NY 11201, USA aronov@ziggy.poly.edu , US;(2) Division of Computer Science, Mathematics, and Science, St. Johns University, Jamaica, NY 11439, USA davisa@stjohns.edu , JM;(3) Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, India 721302 {dey,spp}@cse.iitkgp.ernet.in, IN |
| |
| 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 . Received March 14, 1996, and in revised form December 22, 1997, and January 5, 1998. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
