知道 k 最近邻的情况下计算 Voronoi 图的快速方法
我知道从 Voronoi 细分中计算 k 最近邻集相对容易。那么反向问题呢？ 我已经有了一组 k 最近邻（在 3D 中），并且我想计算 Voronoi 单元的体积和中心。直观上，应该有一个 O(n) 算法可以做到这一点，对吗？
有没有人在某处见过类似的东西？
提前致谢
PS：我假设没有任何 Voronoi 单元具有超过 k 个边（有关点位置的先验知识可能使得在 O(n) 中计算图成为可能，与维数无关）。
PPS：我进一步假设对于给定点，Voronoi 单元的顶点属于 kNN 集合（请参阅下面的评论）。
I know it is relatively easy to compute the sets of k-nearest neighbours from a Voronoi tessellations. What about the reverse problem?
I already have the set of k-nearest neighbours (in 3D) and I would like to compute the volumes and centres of the Voronoi cells. Intuitively, there should be an O(n) algorithm that does that, right?
Has anyone seen something like this implemented somewhere?
Thanks in advance
PS: I assume that no Voronoi cell has more than k edges (this prior knowledge on the location of the points is probably what makes it possible to compute the diagram in O(n), independently of the dimensionality).
PPS: I further assume that for a given point, the vertices of the Voronoi cell belong to the set of kNN (see comments below).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以按如下方式构建 VD。点 P 及其 k 个最近邻点 Q 之一定义与 P 和 Q 等距的半平面 H(P,Q)，以及具有边界 H 并包含 P 的半空间 H+(P,Q)。然后P 的单元格是 P 的 k 个最近邻中所有 Q 的 H+(P,Q) 的交集。
构建此交集与顶点枚举问题密切相关：http://en.wikipedia.org/wiki/ Vertex_enumeration_problem
您需要有足够的邻居来确保构建正确的 VD，但我不确定您的假设是否能保证这一点。唯一确定的是，点 P 的真实 Voronoi 单元包含在上述算法构建的单元中。
You can build the VD as follows. A point P and one of its k nearest neighbors Q define a half-plane H(P,Q) equidistant to both P and Q, and a half-space H+(P,Q) with boundary H and containing P. Then the Voronoi cell of P is the intersection of the H+(P,Q) for all Q in the k nearest neighbors of P.
Building this intersection is very closely related to the Vertex Enumeration Problem: http://en.wikipedia.org/wiki/Vertex_enumeration_problem
You need to have enough neighbors to be sure that the correct VD is constructed and I'm not sure that your assumptions guarantee that. The only sure thing is that the real Voronoi cell of a point P is included in the cell that the algorithm above constructs.
虽然应该有一种直观的算法，但我认为实际上并不存在。虽然我没有正式的证明（并且无法那么快地证明），但请考虑以下论点：
考虑点 P 的 k 个最近邻点 K 都位于 P 一侧的情况，即有一个穿过 P 的平面，使得 K 中的所有点都在平面的一侧。那么 P 的 Voronoi 单元的边界就无法以任何方式从 K 中的点计算出来。这个论点对于任何 k 都成立，而且我看不出算法如何检测 K 上任何点的存在。通过最近邻分析计算 P 的另一边。因此，我认为 Voronoi 图比 k 最近邻统计包含更多信息，因此从 Voronoi 到 kNN 的转换是不可逆的减少。
另一方面，Hugo Ledoux 开发了一种用于 Voronoization 的 log n 平均情况算法，您可以考虑该解决方案。
编辑：我的论点可能仍然太复杂。关于 kNN 的简单思考：考虑一个由 k 个点组成的簇，这些点是彼此的 kNN。这些点的 kNN 子图与所有其他点断开连接，使得构建 Voronoi 图变得不可能。或者，换句话说，Voronoi 图包含任何 k 的 k 个最近邻，因此无法从任何有限 k 重建。
While there should be an intuitive algorithm, I don't think that there actually is one. While I have no formal proof (and couldn't make one up that fast), consider the following argument:
Consider the case where the k-nearest neighbouring points K of a point P are all to one side of P, i.e. there is a plane through P such that all points in K are on one side of the plane. The boundary of the Voronoi cell of P can then not be computed, in any way, from the points in K. This argument holds for any k, and I can't see any way how an algorithm could detect the presence of any point on the other side of P by nearest-neighbour analysis. Therefore, I argue that the Voronoi diagram contains more information than the k-nearest neighbours statistic and therefore the transformation from Voronoi to kNN is an irreversible reduction.
On the other hand, Hugo Ledoux has developed a n log n average case algorithm for Voronoization, you might consider that solution.
Edit: My argument is probably still too complex. Simple thought about kNN: Consider a cluster of k points that are the kNN to each other. The kNN subgraph for these points is disconnected from all other points, making the construction of a Voronoi diagram impossible. Or, in other terms, the Voronoi diagram contains the k-nearest neighbours for any k, thus cannot be reconstructed from any finite k.