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 proceedingConference contribution

24 Scopus citations


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 languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 18th International Colloquium, Proceedings
EditorsJavier Leach Albert, Mario Rodriguez Artalejo, Burkhard Monien
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783540542339
StatePublished - 1991
Event18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991 - Madrid, Spain
Duration: Jul 8 1991Jul 12 1991

Publication series

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


Other18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Ray shooting in polygons using geodesic triangulations'. Together they form a unique fingerprint.

Cite this