Farthest-Polygon Voronoi Diagrams - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

Farthest-Polygon Voronoi Diagrams

Résumé

Given a family of k disjoint connected polygonal sites 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.
Fichier principal
Vignette du fichier
ESA.pdf (282.29 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00189038 , version 1 (19-11-2007)

Identifiants

Citer

Otfried Cheong, Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, et al.. Farthest-Polygon Voronoi Diagrams. 15th Annual European Symposium on Algorithms - ALGO 2007, Oct 2007, Eilat, Israel. pp.407-418, ⟨10.1007/978-3-540-75520-3_37⟩. ⟨inria-00189038⟩
190 Consultations
157 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More