Visibility with multiple reflections

Boris Aronov; Alan R. Davis; Tamal K. Dey; Sudebkumar P. Pal; D. Chithra Prasad

doi:10.1007/3-540-61422-2_139

Visibility with multiple reflections

Boris Aronov, Alan R. Davis, Tamal K. Dey, Sudebkumar P. Pal, D. Chithra Prasad

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We show that the region lit by a point fight 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)^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 any k>1.

Original language	English (US)
Title of host publication	Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings
Editors	Rolf Karlsson, Andrzej Lingas
Publisher	Springer Verlag
Pages	284-295
Number of pages	12
ISBN (Print)	3540614222, 9783540614227
DOIs	https://doi.org/10.1007/3-540-61422-2_139
State	Published - 1996
Event	5th Scandinavian Workshop on Algorithm Theory, SWAT 1996 - Reykjavik, Iceland Duration: Jul 3 1996 → Jul 5 1996

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1097
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	5th Scandinavian Workshop on Algorithm Theory, SWAT 1996
Country/Territory	Iceland
City	Reykjavik
Period	7/3/96 → 7/5/96

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-61422-2_139

Cite this

Aronov, B., Davis, A. R., Dey, T. K., Pal, S. P., & Chithra Prasad, D. (1996). Visibility with multiple reflections. In R. Karlsson, & A. Lingas (Eds.), Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings (pp. 284-295). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1097). Springer Verlag. https://doi.org/10.1007/3-540-61422-2_139

Visibility with multiple reflections. / Aronov, Boris; Davis, Alan R.; Dey, Tamal K. et al.
Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings. ed. / Rolf Karlsson; Andrzej Lingas. Springer Verlag, 1996. p. 284-295 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1097).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aronov, B, Davis, AR, Dey, TK, Pal, SP & Chithra Prasad, D 1996, Visibility with multiple reflections. in R Karlsson & A Lingas (eds), Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1097, Springer Verlag, pp. 284-295, 5th Scandinavian Workshop on Algorithm Theory, SWAT 1996, Reykjavik, Iceland, 7/3/96. https://doi.org/10.1007/3-540-61422-2_139

Aronov B, Davis AR, Dey TK, Pal SP, Chithra Prasad D. Visibility with multiple reflections. In Karlsson R, Lingas A, editors, Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings. Springer Verlag. 1996. p. 284-295. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-61422-2_139

Aronov, Boris ; Davis, Alan R. ; Dey, Tamal K. et al. / Visibility with multiple reflections. Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings. editor / Rolf Karlsson ; Andrzej Lingas. Springer Verlag, 1996. pp. 284-295 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{44b8fe056ee94114a0392f3846e6e918,

title = "Visibility with multiple reflections",

abstract = "We show that the region lit by a point fight 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)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 any k>1.",

author = "Boris Aronov and Davis, {Alan R.} and Dey, {Tamal K.} and Pal, {Sudebkumar P.} and {Chithra Prasad}, D.",

year = "1996",

doi = "10.1007/3-540-61422-2_139",

language = "English (US)",

isbn = "3540614222",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "284--295",

editor = "Rolf Karlsson and Andrzej Lingas",

booktitle = "Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings",

note = "5th Scandinavian Workshop on Algorithm Theory, SWAT 1996 ; Conference date: 03-07-1996 Through 05-07-1996",

}

TY - GEN

T1 - Visibility with multiple reflections

AU - Aronov, Boris

AU - Davis, Alan R.

AU - Dey, Tamal K.

AU - Pal, Sudebkumar P.

AU - Chithra Prasad, D.

PY - 1996

Y1 - 1996

N2 - We show that the region lit by a point fight 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)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 any k>1.

AB - We show that the region lit by a point fight 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)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 any k>1.

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

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

U2 - 10.1007/3-540-61422-2_139

DO - 10.1007/3-540-61422-2_139

M3 - Conference contribution

AN - SCOPUS:21344439275

SN - 3540614222

SN - 9783540614227

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 284

EP - 295

BT - Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Karlsson, Rolf

A2 - Lingas, Andrzej

PB - Springer Verlag

T2 - 5th Scandinavian Workshop on Algorithm Theory, SWAT 1996

Y2 - 3 July 1996 through 5 July 1996

ER -

Visibility with multiple reflections

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this