我知道从 Voronoi 镶嵌中计算 k 最近邻的集合相对容易。反过来的问题呢？ 我已经有了一组 k 最近邻(在 3D 中)，我想计算 Voronoi 单元的体积和中心。直觉上，应该有一个 O(n) 算法可以做到这一点，对吧？
有没有人在某处看到过类似的实现？
提前致谢
PS:我假设没有 Voronoi 单元具有超过 k 条边(这种关于点位置的先验知识可能使得在 O(n) 中计算图成为可能，与维数无关)。
PPS:我进一步假设对于给定的点，Voronoi 单元的顶点属于 kNN 的集合(见下面的评论)。
最佳答案
您可以按如下方式构建 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/Vertex_enumeration_problem
您需要有足够多的邻居来确保构建正确的 VD，但我不确定您的假设是否能保证这一点。唯一确定的是点P的真实Voronoi元胞包含在上述算法构造的元胞中。
关于algorithm - 知道 k 最近邻的快速计算 Voronoi 图的方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7983456/