Farthest-Polygon Voronoi Diagrams

DOI10.1007/978-3-540-75520-3_37MaRDI QIDQ3527230zbMATH OpenOpenAlexFDO

Authors Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, Sylvain Lazard, Hyeon-Suk Na, Otfried Cheong, Mira Lee

Publication date 25 September 2008

Published in Algorithms – ESA 2007 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.3593

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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.

Recommendations

• Farthest-polygon Voronoi diagrams
• The geodesic farthest-point Voronoi diagram in a simple polygon
• The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon
• The furthest-site geodesic Voronoi diagram
• The geodesic farthest-site Voronoi diagram in a polygonal domain with holes

Cited in

(17)

• Voronoi diagrams for polygon-offset distance functions
• Improved algorithms for the farthest colored Voronoi diagram of segments
• On the central path problem
• On farthest Voronoi cells
• 2-point site Voronoi diagrams
• On the Farthest Line-Segment Voronoi Diagram
• Voronoi diagram for convex polygonal sites with convex polygon-offset distance function
• Euclidean farthest-point Voronoi diagram of a digital edge
• The weighted farthest color Voronoi diagram on trees and graphs.
• Solving the chromatic cone clustering problem via minimum spanning sphere
• Farthest-polygon Voronoi diagrams
• FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
• Voronoi diagrams for convex polygon-offset distance functions
• The geodesic farthest-site Voronoi diagram in a polygonal domain with holes
• A radius of robust feasibility for uncertain farthest Voronoi cells
• Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments
• On farthest Bregman Voronoi cells

This page was built for publication: Farthest-Polygon Voronoi Diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3527230)