The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites

DOI10.1145/1998196.1998234MaRDI QIDQ5404431zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Reem

Publication date 24 March 2014

Published in Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)

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

zbMATH Keywords

shapeHausdorff distancecontinuityperturbationVoronoi diagramsiteapproximateVoronoi cellgeometric stabilityuniformly convex normed spacesmall change

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Voronoi diagrams appear in many areas in science and technology and have numerous applications. They have been the subject of extensive investigation during the last decades. Roughly speaking, they are a certain decomposition of a given space into cells, induced by a distance function and by a tuple of subsets called the generators or the sites. Consider the following question: does a small change of the sites, e.g., of their position or shape, yield a small change in the corresponding Voronoi cells? This question is by all means natural and fundamental, since in practice one approximates the sites either because of inexact information about them, because of inevitable numerical errors in their representation, for simplification purposes and so on, and it is important to know whether the resulting Voronoi cells approximate the real ones well. The traditional approach to Voronoi diagrams, and, in particular, to (variants of) this question, is combinatorial. However, it seems that there has been a very limited discussion in the geometric sense (the shape of the cells), mainly an intuitive one, without proofs, in Euclidean spaces. We formalize this question precisely, and then show that the answer is positive in the case of R^d, or, more generally, in (possibly infinite dimensional) uniformly convex normed spaces, assuming there is a common positive lower bound on the distance between the sites. Explicit bounds are given, and we allow infinitely many sites of a general form. The relevance of this result is illustrated using several pictures and many real-world and theoretical examples and counterexamples.

Recommendations

• On the stability of Voronoi cells
• On the geodesic Voronoi diagram of point sites in a simple polygon
• On the structural properties of Voronoi diagrams
• On 2-site Voronoi diagrams under geometric distance functions
• The geodesic farthest-site Voronoi diagram in a polygonal domain with holes
• The stability of Delaunay triangulations
• Stable-matching Voronoi diagrams: combinatorial complexity and algorithms
• Stable-matching Voronoi diagrams: combinatorial complexity and algorithms
• Approximating Voronoi Diagrams of Convex Sites in Any Dimension
• A compact piecewise-linear Voronoi diagram for convex sites in the plane

Cited in

(9)

• On metric regularity of Voronoi cells
• Zone diagrams in compact subsets of uniformly convex normed spaces
• Brillouin zones of integer lattices and their perturbations
• Voronoi polytopes for polyhedral norms on lattices
• The Voronoi inverse mapping
• On the stability of Voronoi cells
• On the computation of zone and double zone diagrams
• Zero-convex functions, perturbation resilience, and subgradient projections for feasibility-seeking methods
• Voronoi Diagram and Delaunay Triangulation with Independent and Dependent Geometric Uncertainties

This page was built for publication: The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites

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