Farthest-Polygon Voronoi Diagrams - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Computational Geometry Année : 2011

Farthest-Polygon Voronoi Diagrams

Résumé

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.
Fichier principal
Vignette du fichier
final.pdf (311.33 Ko) Télécharger le fichier
Vignette du fichier
2011 Farthest-Polygon Voronoi Diagrams.png (50.69 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...

Dates et versions

inria-00442816 , version 1 (22-12-2009)
inria-00442816 , version 2 (20-01-2010)
inria-00442816 , version 3 (29-11-2010)

Identifiants

Citer

Otfried Cheong, Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, et al.. Farthest-Polygon Voronoi Diagrams. Computational Geometry, 2011, Computational Geometry, Theory and Applications, 44 (4), pp.14. ⟨10.1016/j.comgeo.2010.11.004⟩. ⟨inria-00442816v3⟩
438 Consultations
1005 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More