On the stability of Voronoi cells

Abstract

Let T be a given subset of ℝ n , whose elements are called sites, and let s∈T. The Voronoi cell of s with respect to T consists of all points closer to s than to any other site. In many real applications, the position of some elements of T is uncertain due to either random external causes or to measurement errors. In this paper we analyze the effect on the Voronoi cell of small changes in s or in a given non-empty set P⊂T\{s}. Two types of perturbations of P are considered, one of them not increasing the cardinality of T. More in detail, the paper provides conditions for the corresponding Voronoi cell mappings to be closed, lower and upper semicontinuous. All the involved conditions are expressed in terms of the data.