我需要一种算法来计算 O(n) 中点的 Voronoi 图的一组点的凸包。Voronoi 图包含在边界框中，并存储为双向连接的边列表。输入是一个半边，其原点在边界框上。
我知道两个点在凸包上是相邻的，如果它们共享一个无限长的 voronoi 边。
问问题
1917 次
2 回答
2
如果您有一个足够大的边界框，以至于只有无限单元格具有边界边缘，那么这项任务似乎并不难。遍历边界边，对于它们中的每一个，向前和向后遍历它以找到第一个非边界边F和B。将遍历过程中找到的当前和所有边界标记为used。如果盒子不存在，边缘F和B将是无限的。因此，它们接触的面 (fF和fB) 的“中心”是凸包的一部分（当前面是C），而交叉边C-to-F是凸包的一部分。取脸fF并从 的双胞胎向前迭代F以找到下一个非边界边，例如F1。如果它等于'B'-twin（或者它的边界是used）， 我们结束了。如果不是，则遍历下一个邻居（'fF1'）。
于 2011-01-27T22:28:27.953 回答
-1
我相信可以在 O(n) 时间内计算出 Voronoi 图的凸包。
对于给定的 Voronoi 图和应驻留在 CH 中的顶点，您可以迭代 Voronoi 图的单元并扩展凸包，就像在 Grahm 扫描算法中所做的那样，但方式不同。
这里只缺少一个理论，接下来看...
根据 Springer 的 M4 书《计算几何》，定理 7.4：当且仅当其最大的空圆 C_p(q) 在其边界上包含三个或更多站点时，点 q 是 Vor(P) 的顶点。这意味着每次迭代都需要检查的站点是在 O(1) 中完成的，这意味着您只需遍历 O(n) 个站点。
根据定理 7.3，一个 ste 的 n 个点的 Voronoi 图的顶点数在一个平原上最多为 2n-5（线性顺序）。
因此可以在 O(n) 时间内计算 Voronoi 图的 CH。
于 2014-07-13T18:57:35.253 回答