The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites
The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites
复制标题
Voronoi图相对于位点微小变化的几何稳定性
DOI：
10.1145/1998196.1998234
复制
发表时间：
2011
影响因子：
5
通讯作者：
W. Schneider
中科院分区：
文献类型：
--
作者：
J. Boike;K. Abramova;D. Bolshiyanov;M. Grigoriev;U. Herzschuh;G. Kattner;C. Knoblauch;L. Kutzbach;G. Mollenhauer;W. Schneider
Voronoi图出现在科学和技术的许多领域，并有许多应用。在过去的几十年里，它们一直是广泛调查的主题。粗略地说，它们是给定空间到单元的某种分解，由距离函数和称为生成元或站点的子集元组引起。考虑以下问题：网站的一个小变化，例如，它们的位置或形状，在相应的Voronoi细胞中产生微小的变化？这个问题无论如何都是自然的和基本的，因为在实践中，人们要么因为关于它们的不精确的信息，要么因为它们的表示中不可避免的数值误差，为了简化目的等等，而近似这些位置，并且重要的是知道所得到的Voronoi单元是否很好地近似真实的单元。传统的方法Voronoi图，特别是这个问题的（变种），是组合。然而，似乎在几何意义上（细胞的形状）有一个非常有限的讨论，主要是一个直观的，没有证据，在欧几里得空间。我们形式化这个问题，然后表明，答案是积极的情况下，路，或者，更一般地说，在（可能是无限维）一致凸赋范空间，假设有一个共同的正下界的网站之间的距离。明确的界限，我们允许无限多个网站的一般形式。这一结果的相关性说明使用几张图片和许多现实世界和理论的例子和反例。
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 Rd, 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.