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.
Type de document :
Communication dans un congrès
ACM Symposium on Computational Geometry, 1999, Miami Beach, Florida, USA, pp.227-236, 1999
Liste complète des métadonnées

https://hal.inria.fr/inria-00108058
Contributeur : Publications Loria <>
Soumis le : jeudi 19 octobre 2006 - 15:40:33
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00108058, version 1

Collections

Citation

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, 1999, Miami Beach, Florida, USA, pp.227-236, 1999. 〈inria-00108058〉

Partager

Métriques

Consultations de la notice

185