Farthest-Polygon Voronoi Diagrams

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.

Domains

Computer Science [cs] Computational Geometry [cs.CG]

Fichier principal

ESA.pdf (282.29 Ko)

Origin : Files produced by the author(s)

Sylvain Lazard : Connect in order to contact the contributor

https://hal.inria.fr/inria-00189038

Submitted on : Monday, November 19, 2007-6:56:33 PM

Last modification on : Friday, November 18, 2022-6:46:07 PM

Long-term archiving on: Monday, April 12, 2010-2:44:40 AM

Dates and versions

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

Identifiers

HAL Id : inria-00189038 , version 1
DOI : 10.1007/978-3-540-75520-3_37

Cite

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⟩

Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

Collections

CNRS INRIA UNIV-LORRAINE INRIA2 LORIA

180 View

152 Download