2

我知道从 Voronoi 镶嵌计算 k 最近邻的集合相对容易。反过来的问题呢？我已经有了一组 k 最近邻（3D），我想计算 Voronoi 单元的体积和中心。直观地说，应该有一个 O(n) 算法可以做到这一点，对吧？

有没有人在某处看到过这样的事情？

提前致谢

PS：我假设没有 Voronoi 单元的边数超过 k （这种关于点位置的先验知识可能使计算 O(n) 中的图表成为可能，与维度无关）。

PPS：我进一步假设对于给定的点，Voronoi 单元的顶点属于 kNN 的集合（见下面的评论）。

4

2 回答 2

1

您可以按如下方式构建 VD。一个点 P 和它的 k 个最近邻点 Q 之一定义了一个与 P 和 Q 等距的半平面 H(P,Q)，以及一个具有边界 H 并包含 P 的半空间 H+(P,Q)。然后 Voronoi P 的单元格是 P 的 k 个最近邻居中所有 Q 的 H+(P,Q) 的交集。建立这个交集与顶点枚举问题密切相关：http ://en.wikipedia.org/wiki/顶点枚举问题

您需要有足够的邻居来确保构建正确的 VD，我不确定您的假设是否能保证这一点。唯一可以确定的是，点 P 的真实 Voronoi 单元包含在上述算法构造的单元中。

于 2011-11-03T12:24:51.057 回答
0

虽然应该有一个直观的算法，但我认为实际上并没有。虽然我没有正式的证据（也不能那么快地做出证明），但请考虑以下论点：

考虑点P的k个最近邻点K都在P的一侧的情况，即存在一个通过P的平面，使得K中的所有点都在该平面的一侧。然后不能以任何方式从 K 中的点计算 P 的 Voronoi 单元的边界。这个论点适用于任何 k，我看不出算法如何检测任何点的存在通过最近邻分析得到 P 的另一侧。因此，我认为 Voronoi 图比 k 最近邻统计包含更多信息，因此从 Voronoi 到 kNN 的转换是不可逆的减少。

另一方面，Hugo Ledoux为 Voronoization 开发了一个 log n 平均案例算法，您可能会考虑该解决方案。

编辑：我的论点可能仍然太复杂。关于 kNN 的简单思考：考虑一组 k 点，它们彼此之间是 kNN。这些点的 kNN 子图与所有其他点断开连接，因此无法构建 Voronoi 图。或者，换句话说，Voronoi 图包含任何k 的 k 最近邻，因此不能从任何有限 k 重构。

于 2011-11-03T10:22:43.823 回答