Farthest-Polygon Voronoi Diagrams

Abstract : 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.
Type de document :
Communication dans un congrès
15th Annual European Symposium on Algorithms - ALGO 2007, Oct 2007, Eilat, Israel. Springer Berlin / Heidelberg, LNCS 4698/2007, pp.407-418, 2007, Lecture Notes in Computer Science. 〈10.1007/978-3-540-75520-3_37〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00189038
Contributeur : Sylvain Lazard <>
Soumis le : lundi 19 novembre 2007 - 18:56:33
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : lundi 12 avril 2010 - 02:44:40

Fichier

ESA.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. 15th Annual European Symposium on Algorithms - ALGO 2007, Oct 2007, Eilat, Israel. Springer Berlin / Heidelberg, LNCS 4698/2007, pp.407-418, 2007, Lecture Notes in Computer Science. 〈10.1007/978-3-540-75520-3_37〉. 〈inria-00189038〉

Partager

Métriques

Consultations de la notice

298

Téléchargements de fichiers

145