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

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00442816
Contributeur : Samuel Hornus <>
Soumis le : lundi 29 novembre 2010 - 11:06:50
Dernière modification le : samedi 27 janvier 2018 - 01:31:40
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

819

Téléchargements de fichiers

266