Dynamic well-spaced point sets
Dynamic well-spaced point sets
复制标题
动态间隔良好的点集
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Duru Türkoglu
中科院分区：
文献类型：
--
作者：
Umut A. Acar;Andrew Cotter;Benoît Hudson;Duru Türkoglu
在一个间距良好的点集中，当存在一个有界超立方体时，沃罗诺伊胞腔都具有有界的纵横比，即从沃罗诺伊位点到沃罗诺伊胞腔中最远点的距离除以到集合中最近邻点的距离是由一个小常数界定的。间距良好的点集满足一些重要的几何性质，并产生高质量的沃罗诺伊或单纯形网格，这在科学计算中可能是很重要的。在本文中，我们考虑动态间距良好的点集问题，该问题需要计算一个动态变化的输入集的间距良好的超集，例如，当输入点被插入或删除时。我们提出了一种动态算法，该算法允许在最坏情况下以\(O(\log\Delta)\)的时间向输入中插入/从输入中删除点，其中\(\Delta\)是几何扩展，当输入点由对数大小的字表示时，它是一个由\(O(\log n)\)界定的自然度量。我们表明动态更新算法在最坏情况下是最优的。我们的算法生成大小最优的输出：所得的输出集永远不会比必要的最小大小大超过一个常数因子。初步实现表明该算法在实践中确实很快。据我们所知，这是第一个针对间距良好的点集的时间和大小均最优的动态算法。
In a well-spaced point set, when there is a bounding hypercube, the Voronoi cells all have bounded aspect ratio, i.e., the distance from the Voronoi site to the farthest point in the Voronoi cell divided by the distance to the nearest neighbor in the set is bounded by a small constant. Well-spaced point sets satisfy some important geometric properties and yield quality Voronoi or simplicial meshes that can be important in scientific computations. In this paper, we consider the dynamic well-spaced point sets problem, which requires computing the well-spaced superset of a dynamically changing input set, e.g., as input points are inserted or deleted. We present a dynamic algorithm that allows inserting/deleting points into/from the input in worst-case O(log Δ) time, where Δ is the geometric spread, a natural measure that is bounded by O(log n) when input points are represented by log-size words. We show that the runtime of the dynamic update algorithm is optimal in the worst case. Our algorithm generates size-optimal outputs: the resulting output sets are never more than a constant factor larger than the minimum size necessary. A preliminary implementation indicates that the algorithm is indeed fast in practice. To the best of our knowledge, this is the first time- and size-optimal dynamic algorithm for well-spaced point sets.