Skip to Main content Skip to Navigation
Conference papers

Hierarchical Vertical Decompositions, Ray Shooting, and Circular Arc Queries 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 new hierarchical decomposition of a simple polygon in introduced. The hierarchy has depth O(log n), linear size, and its regions have maximum degree three. Using this hierarchy, circular ray shooting queries in a simple polygon can be answered in O(log^2n) query time and O(nlogn) space. If the radius of the circle is fixed, the query time can be improved to O(logn) and the space to O(n). The decomposition is also applied to three other circular arc query problems: shortest directed arc, arc bending, and arc pushing. Using these queries, the largest empty lune determined by two query points in a simple polygon can be computed in O(log^3n) time, while the circular visibility region of a query point in a simple polygon can be reported in time O(mlog^3n), where m is the output size.
Document type :
Conference papers
Complete list of metadata
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, October 19, 2006 - 3:40:33 PM
Last modification on : Friday, February 26, 2021 - 3:28:03 PM


  • HAL Id : inria-00108058, version 1



Siu-Wing Cheng, Otfried Cheong, Hazel Everett, Rene van Oostrum. Hierarchical Vertical Decompositions, Ray Shooting, and Circular Arc Queries in Simple Polygons. ACM Symposium on Computational Geometry, Association for Computing Machinery, 1999, Miami Beach, Florida, USA, pp.227-236. ⟨inria-00108058⟩



Les métriques sont temporairement indisponibles