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 - Funding Information:
In this paper we consider the ray 8hooting problem in simple polygons. Given a simple polygon :P with n vertices, we wish to preprocess it into a data structure that supports fast ray-shooting queries inside T', each asking for the first intersection of a query ray with the polygon. This is one of the fundamental problems in plane computational geometry. It has been studied by Chazelle and Guibas [7], who gave a solution with preprocessing °Work by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been supported by NSF Grant CCP~-89-21421. Work by Micha Sharir has been supported by ONIt Grants N00014-89-J-3042 and N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. 1DEC Systems Research Center 2Laboratory for Computer Science, M.I.T. SDepartment of Mathematics, M.I.T. 4Computer Science Department, Princeton University SComputer Science Department, Stanford University 6School of Mathematical Sciences, Tel Aviv University 7Courant Institute of Mathematical Sciences, New York University SComputer Science Department, University of Illinois at Urbana-Champaign
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 -