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.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00189038
Contributor : Sylvain Lazard <>
Submitted on : Monday, November 19, 2007 - 6:56:33 PM
Last modification on : Thursday, February 7, 2019 - 5:53:33 PM
Document(s) archivé(s) le : Monday, April 12, 2010 - 2:44:40 AM

File

ESA.pdf
Files produced by the author(s)

Identifiers

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. pp.407-418, ⟨10.1007/978-3-540-75520-3_37⟩. ⟨inria-00189038⟩

Share

Metrics

Record views

347

Files downloads

172