Ray shooting in polygons using geodesic triangulations

Bernard Chazelle; Herbert Edelsbrunner; Michelangelo Grigni; Leonidas Guibas; John Hershberger; Micha Sharir; Jack Snoeyink

doi:10.1007/3-540-54233-7_172

Ray shooting in polygons using geodesic triangulations

Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, John Hershberger, Micha Sharir, Jack Snoeyink

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

24 Scopus citations

Abstract

Let P be a simple polygon with n vertices. We present a simple decomposition scheme that partitions the interior of P into O(n) so-called geodesic triangles, so that any line segment interior to P crosses at most 2 log n of these triangles. This decomposition can be used to preprocess P in time O(n log n) and storage O(n), so that any ray-shooting query can be answered in time O(log n). The algorithms are fairly simple and easy to implement. We also extend this technique to the case of ray-shooting amidst k polygonal obstacles with a total of n edges, so that a query can be answered in 0(√k log n) time.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 18th International Colloquium, Proceedings
Editors	Javier Leach Albert, Mario Rodriguez Artalejo, Burkhard Monien
Publisher	Springer Verlag
Pages	661-673
Number of pages	13
ISBN (Print)	9783540542339
DOIs	https://doi.org/10.1007/3-540-54233-7_172
State	Published - 1991
Externally published	Yes
Event	18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991 - Madrid, Spain Duration: Jul 8 1991 → Jul 12 1991

Publication series

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

Other

Other	18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991
Country/Territory	Spain
City	Madrid
Period	7/8/91 → 7/12/91

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-54233-7_172

Cite this

Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Hershberger, J., Sharir, M., & Snoeyink, J. (1991). Ray shooting in polygons using geodesic triangulations. In J. L. Albert, M. R. Artalejo, & B. Monien (Eds.), Automata, Languages and Programming - 18th International Colloquium, Proceedings (pp. 661-673). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 510 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-54233-7_172

Chazelle, Bernard ; Edelsbrunner, Herbert ; Grigni, Michelangelo et al. / Ray shooting in polygons using geodesic triangulations. Automata, Languages and Programming - 18th International Colloquium, Proceedings. editor / Javier Leach Albert ; Mario Rodriguez Artalejo ; Burkhard Monien. Springer Verlag, 1991. pp. 661-673 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b050b95e8e96459db3d9915948725331,

title = "Ray shooting in polygons using geodesic triangulations",

abstract = "Let P be a simple polygon with n vertices. We present a simple decomposition scheme that partitions the interior of P into O(n) so-called geodesic triangles, so that any line segment interior to P crosses at most 2 log n of these triangles. This decomposition can be used to preprocess P in time O(n log n) and storage O(n), so that any ray-shooting query can be answered in time O(log n). The algorithms are fairly simple and easy to implement. We also extend this technique to the case of ray-shooting amidst k polygonal obstacles with a total of n edges, so that a query can be answered in 0(√k log n) time.",

author = "Bernard Chazelle and Herbert Edelsbrunner and Michelangelo Grigni and Leonidas Guibas and John Hershberger and Micha Sharir and Jack Snoeyink",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; 18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991 ; Conference date: 08-07-1991 Through 12-07-1991",

year = "1991",

doi = "10.1007/3-540-54233-7_172",

language = "English (US)",

isbn = "9783540542339",

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

publisher = "Springer Verlag",

pages = "661--673",

editor = "Albert, {Javier Leach} and Artalejo, {Mario Rodriguez} and Burkhard Monien",

booktitle = "Automata, Languages and Programming - 18th International Colloquium, Proceedings",

address = "Germany",

}

Chazelle, B, Edelsbrunner, H, Grigni, M, Guibas, L, Hershberger, J, Sharir, M & Snoeyink, J 1991, Ray shooting in polygons using geodesic triangulations. in JL Albert, MR Artalejo & B Monien (eds), Automata, Languages and Programming - 18th International Colloquium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 510 LNCS, Springer Verlag, pp. 661-673, 18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991, Madrid, Spain, 7/8/91. https://doi.org/10.1007/3-540-54233-7_172

Ray shooting in polygons using geodesic triangulations. / Chazelle, Bernard; Edelsbrunner, Herbert; Grigni, Michelangelo et al.
Automata, Languages and Programming - 18th International Colloquium, Proceedings. ed. / Javier Leach Albert; Mario Rodriguez Artalejo; Burkhard Monien. Springer Verlag, 1991. p. 661-673 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 510 LNCS).

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

TY - GEN

T1 - Ray shooting in polygons using geodesic triangulations

AU - Chazelle, Bernard

AU - Edelsbrunner, Herbert

AU - Grigni, Michelangelo

AU - Guibas, Leonidas

AU - Hershberger, John

AU - Sharir, Micha

AU - Snoeyink, Jack

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1991.

PY - 1991

Y1 - 1991

N2 - Let P be a simple polygon with n vertices. We present a simple decomposition scheme that partitions the interior of P into O(n) so-called geodesic triangles, so that any line segment interior to P crosses at most 2 log n of these triangles. This decomposition can be used to preprocess P in time O(n log n) and storage O(n), so that any ray-shooting query can be answered in time O(log n). The algorithms are fairly simple and easy to implement. We also extend this technique to the case of ray-shooting amidst k polygonal obstacles with a total of n edges, so that a query can be answered in 0(√k log n) time.

AB - Let P be a simple polygon with n vertices. We present a simple decomposition scheme that partitions the interior of P into O(n) so-called geodesic triangles, so that any line segment interior to P crosses at most 2 log n of these triangles. This decomposition can be used to preprocess P in time O(n log n) and storage O(n), so that any ray-shooting query can be answered in time O(log n). The algorithms are fairly simple and easy to implement. We also extend this technique to the case of ray-shooting amidst k polygonal obstacles with a total of n edges, so that a query can be answered in 0(√k log n) time.

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

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

U2 - 10.1007/3-540-54233-7_172

DO - 10.1007/3-540-54233-7_172

M3 - Conference contribution

AN - SCOPUS:0040952081

SN - 9783540542339

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

SP - 661

EP - 673

BT - Automata, Languages and Programming - 18th International Colloquium, Proceedings

A2 - Albert, Javier Leach

A2 - Artalejo, Mario Rodriguez

A2 - Monien, Burkhard

PB - Springer Verlag

T2 - 18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991

Y2 - 8 July 1991 through 12 July 1991

ER -

Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Hershberger J, Sharir M et al. Ray shooting in polygons using geodesic triangulations. In Albert JL, Artalejo MR, Monien B, editors, Automata, Languages and Programming - 18th International Colloquium, Proceedings. Springer Verlag. 1991. p. 661-673. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-54233-7_172

Ray shooting in polygons using geodesic triangulations

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this