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).
Type de document :
Article dans une revue
Discrete and Computational Geometry, Springer Verlag, 2004, 32 (3), pp.401-415. 〈10.1007/s00454-004-1098-2〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00100017
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:13:22
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Lien texte intégral

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

196