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 -