Visibility with multiple reflections

B. Aronov; A. R. Davis; T. K. Dey; S. P. Pal; D. C. Prasad

doi:10.1007/PL00009378

Visibility with multiple reflections

B. Aronov, A. R. Davis, T. K. Dey, S. P. Pal, D. C. Prasad

Research output: Contribution to journal › Article › peer-review

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^2klog n) time and O(n^2k) space for k ≥ 1, and in O(n² log² n) time and O(n²) space for k = 1.

Original language	English (US)
Pages (from-to)	61-78
Number of pages	18
Journal	Discrete and Computational Geometry
Volume	20
Issue number	1
DOIs	https://doi.org/10.1007/PL00009378
State	Published - Jul 1998

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/PL00009378

Cite this

@article{9401797ace06481cb6f07bc0c83bfdd3,

title = "Visibility with multiple reflections",

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(n2klog n) time and O(n2k) space for k ≥ 1, and in O(n2 log2 n) time and O(n2) space for k = 1.",

author = "B. Aronov and Davis, {A. R.} and Dey, {T. K.} and Pal, {S. P.} and Prasad, {D. C.}",

year = "1998",

month = jul,

doi = "10.1007/PL00009378",

language = "English (US)",

volume = "20",

pages = "61--78",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Visibility with multiple reflections

AU - Aronov, B.

AU - Davis, A. R.

AU - Dey, T. K.

AU - Pal, S. P.

AU - Prasad, D. C.

PY - 1998/7

Y1 - 1998/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032388329&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032388329&partnerID=8YFLogxK

U2 - 10.1007/PL00009378

DO - 10.1007/PL00009378

M3 - Article

AN - SCOPUS:0032388329

SN - 0179-5376

VL - 20

SP - 61

EP - 78

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

Visibility with multiple reflections

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this