Ray shooting in polygons using geodesic triangulations

B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, J. Snoeyink

Research output: Contribution to journalArticle

124 Scopus citations

Abstract

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 a very simple manner, so that any ray-shooting query can be answered in time O(log n). The data structure requires O(n) storage and O(n log n) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time to O(n). We also extend our general 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 O(√ log n) time.

Original languageEnglish (US)
Pages (from-to)54-68
Number of pages15
JournalAlgorithmica
Volume12
Issue number1
DOIs
StatePublished - Jul 1 1994

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Computational geometry
  • Ray-shooting
  • Triangulation

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

  • Cite this

    Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Hershberger, J., Sharir, M., & Snoeyink, J. (1994). Ray shooting in polygons using geodesic triangulations. Algorithmica, 12(1), 54-68. https://doi.org/10.1007/BF01377183