计算Voronoi单元的边界长度

Question

计算Voronoi单元边界的最有效算法是什么？更具体地说，假设我们有一个点列表(在二维中，以简化问题)：P1，P2，P3.Pn现在，如果我只想找到一个随机点的Voronoi单元的边界长度，比如说Pi，它与另一个相邻点Pj共享，有有效的算法吗？

谢谢！

Answer 1

我现在有了这个问题的解决方案，但我不确定它对许多维度是否足够有效。让我重新定义一下这个问题。

问题：假设我们的点列表是{P1，P2，P3，…Pk，X}，并且我们的查询点是X；即，我们感兴趣的是找到Pi的Voronoi细胞和X的Voronai细胞之间共享的小平面的超体积(在二维中为共享边缘的长度)。

解决方案：

1. 我们发现一组点CC={T1，T2，T3，…Tk-1}，它们是点{Pi，X，Pj}的圆心，其中j<>i和1<j<k.这可以在O(k)中完成

2. 从集合CC中，我们可以去除不在X的Voronoi单元内的点。这可以在O(k^2)中完成，并且不需要计算任何Voronoi图。

3. 集合CC中剩下的其余点将完全定义Pi的Voronoi单元和X的Voronai单元之间共享的边界面。在二维中，我们将在集合CC中只剩下两个点(共享边的端点)，从中我们可以很容易地找到长度。

4. 现在，既然我们已经定义了边界面，我们就可以在多项式时间内很容易地找到这个面的近似体积。