HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Hierarchical decompositions and circular ray shooting in simple polygons

Siu-Wing Cheng Otfried Cheong Hazel Everett 1 Rene van Oostrum
1 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A hierarchical decomposition of a simple polygon is introduced. The hierarchy has logarithmic depth, linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray shooting queries in a simple polygon on n vertices can be answered in O(log2 n) query time and O(n log n) space. If the radius of the circle is fixed, the query time can be improved to O(log n) and the space to O(n).
keyword : visibility computational geometry visibilité géometrie algorithmique
Document type :
Journal articles
Complete list of metadata
https://hal.inria.fr/inria-00100017
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 10:13:22 AM
Last modification on : Friday, February 4, 2022 - 3:31:27 AM

Links full text

openaccess

Identifiers

Collections

INRIA | CNRS | LORIA | UNIV-LORRAINE | INRIA2

Citation

Siu-Wing Cheng, Otfried Cheong, Hazel Everett, Rene van Oostrum. Hierarchical decompositions and circular ray shooting in simple polygons. Discrete and Computational Geometry, Springer Verlag, 2004, 32 (3), pp.401-415. ⟨10.1007/s00454-004-1098-2⟩. ⟨inria-00100017⟩

Export

BibTeX TEI DC DCterms EndNote Datacite

Share

Metrics

Record views

84

Designed by Inria-IES Team : http://hal.inria.fr/    Hosted by HAL : http://hal.archives-ouvertes.fr/