Computer Science – Computational Geometry
Scientific paper
2011-03-21
Extended abstract in: Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG 2011), pp. 254-263
Computer Science
Computational Geometry
30 pages (13 pages in appendices); a few corrections and additions, mainly regarding the references and the counterexamples; m
Scientific paper
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.
No associations
LandOfFree
The geometric stability of Voronoi diagrams with respect to small changes of the sites does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The geometric stability of Voronoi diagrams with respect to small changes of the sites, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The geometric stability of Voronoi diagrams with respect to small changes of the sites will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-324208