Farthest-Polygon Voronoi Diagrams

Otfried Cheong 1 Hazel Everett 2 Marc Glisse 3 Joachim Gudmundsson 4 Samuel Hornus 5, * Sylvain Lazard 2 Mira Lee 1 Hyeon-Suk Na 6
* Auteur correspondant
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
5 ALICE - Geometry and Lighting
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(n log^3 n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k-1 connected components, but if one component is bounded, then it is equal to the entire region.
Type de document :
Article dans une revue
Computational Geometry, Elsevier, 2011, Computational Geometry, Theory and Applications, 44 (4), 14 p. <10.1016/j.comgeo.2010.11.004>
Liste complète des métadonnées


https://hal.inria.fr/inria-00442816
Contributeur : Samuel Hornus <>
Soumis le : lundi 29 novembre 2010 - 11:06:50
Dernière modification le : jeudi 9 février 2017 - 15:47:53
Document(s) archivé(s) le : vendredi 2 décembre 2016 - 14:14:39

Fichiers

final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Otfried Cheong, Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, et al.. Farthest-Polygon Voronoi Diagrams. Computational Geometry, Elsevier, 2011, Computational Geometry, Theory and Applications, 44 (4), 14 p. <10.1016/j.comgeo.2010.11.004>. <inria-00442816v3>

Partager

Métriques

Consultations de
la notice

715

Téléchargements du document

231