Farthest-Polygon Voronoi Diagrams

Otfried Cheong 1 Hazel Everett 2 Marc Glisse 3 Joachim Gudmundsson 4 Samuel Hornus 5, * Sylvain Lazard 2 Mira Lee 1 Hyeon-Suk Na 6
* Corresponding author
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
5 ALICE - Geometry and Lighting
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download


https://hal.inria.fr/inria-00442816
Contributor : Samuel Hornus <>
Submitted on : Monday, November 29, 2010 - 11:06:50 AM
Last modification on : Friday, September 20, 2019 - 4:56:38 PM

Files

final.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. Computational Geometry, Elsevier, 2011, Computational Geometry, Theory and Applications, 44 (4), pp.14. ⟨10.1016/j.comgeo.2010.11.004⟩. ⟨inria-00442816v3⟩

Share

Metrics

Record views

870

Files downloads

564