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 -