Hierarchical Vertical Decompositions, Ray Shooting, and Circular Arc Queries in Simple Polygons - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 1999

Hierarchical Vertical Decompositions, Ray Shooting, and Circular Arc Queries in Simple Polygons

Siu-Wing Cheng
  • Fonction : Auteur
Otfried Cheong
  • Fonction : Auteur
Rene van Oostrum
  • Fonction : Auteur

Résumé

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.
Fichier non déposé

Dates et versions

inria-00108058 , version 1 (19-10-2006)

Identifiants

  • HAL Id : inria-00108058 , version 1

Citer

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⟩
109 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More