Farthest-Polygon Voronoi Diagrams - Archive ouverte HAL Access content directly
Journal Articles Computational Geometry Year : 2011

Farthest-Polygon Voronoi Diagrams

(1) , (2) , (3) , (4) , (5) , (2) , (1) , (6)
1
2
3
4
5
6

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.
Vignette du fichier
2011 Farthest-Polygon Voronoi Diagrams.png (50.69 Ko) Télécharger le fichier Fichier principal
Vignette du fichier
final.pdf (311.33 Ko) Télécharger le fichier
Format : Figure, Image
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
413 View
927 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More