An Algorithm for Computing Voronoi Diagrams of General Generators in General Normed Spaces
An Algorithm for Computing Voronoi Diagrams of General Generators in General Normed Spaces
复制标题
计算一般赋范空间中一般生成器 Voronoi 图的算法
DOI：
10.1109/isvd.2009.23
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Daniel Reem
中科院分区：
文献类型：
--
作者：
Daniel Reem
Voronoi图出现在科学和技术的许多领域，并有不同的应用。粗略地说，它们是将给定空间分解成单元，由距离函数和称为生成器或站点的子集元组诱导。在过去的35年中，Voronoi图一直是广泛研究的主题，并且已经发表了许多计算它们的算法。然而，这些算法是针对特定情况的。它们对空间（通常是$R^2$或$R^3$）、生成器（不同的点、特殊的形状）、距离函数（欧几里得函数或其变体）等施加限制。此外，它们的实施并不总是简单的，它们的成功并不总是得到保证。我们提出了一种在一般赋范空间（可能是无限维空间）中计算Voronoi图的简单有效的算法。我们允许有无限多个一般形式的生成器。该算法独立计算每个Voronoi细胞，并达到所需的精度。它可以推广到其他设置，如流形，图和凸距离函数。
Voronoi diagrams appear in many areas in science and technology and have diverse applications. 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. Voronoi diagrams have been the subject of extensive research during the last 35 years, and many algorithms for computing them have been published. However, these algorithms are for specific cases. They impose restrictions on either the space (often $R^2$ or $R^3$), the generators (distinct points, special shapes), the distance function (Euclidean or variations thereof) and more. Moreover, their implementation is not always simple and their success is not always guaranteed. We present an efficient and simple algorithm for computing Voronoi diagrams in general normed spaces, possibly infinite dimensional. We allow infinitely many generators of a general form. The algorithm computes each of the Voronoi cells independently of the others, and to any required precision. It can be generalized to other settings, such as manifolds, graphs and convex distance functions.