Visibility with Multiple Reflections
Visibility with Multiple Reflections
复制标题
多次反射的可见性
DOI：
10.1007/3-540-61422-2_139
复制
发表时间：
1996
影响因子：
0.8
通讯作者：
D. Prasad
中科院分区：
文献类型：
--
作者：
B. Aronov;Alan R. Davis;T. Dey;S. P. Pal;D. Prasad
抽象的。我们证明，对于任何 k≥ 1 ，在最多 k 次边界反射后，由简单 n 边形内的点光源照亮的区域具有组合复杂度 O(n2k) 。还建立了 Ω ((n/k-θ(1))2k) 的下限，该下限与任何固定 k 的上限相匹配。提出了一种用于计算照明区域的简单近最优算法，当 k>1 时，该算法在 O(n2k log n) 时间和 O(n2k) 空间中运行；当 k=1 时，该算法在 O(n2 log2 n) 时间和 O(n2) 空间中运行。
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(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(n2k log n) time and O(n2k) space for k>1 , and in O(n2 log2 n) time and O(n2) space for k=1 .