ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

Visibility with Multiple Reflections (1998)

Aronov, B. ; Davis, A. R. ; Dey, T. K. ; [et al.]

Springer

Discrete & computational geometry 20 (1998), S. 61-78

add to mindlist on the mindlist

Details

ISSN: 1432-0444

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: 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 .

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/PL00009378

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit