  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.
