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

PY - 1991/1/1

Y1 - 1991/1/1

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 -