根据 R. A. Dwyer, Algorithmica 2.1-4 (1987): 137-151可以在 O(N lnlnN) 时间内构建单位正方形中 N 个点均匀分布的 Delaunay 三角剖分。我想知道目前已知最快的为立方晶胞中的均匀分布构建 Delaunay 图的顺序算法是什么？
最佳答案
TL; DR:我期望立方体中一组“分布良好”的点具有准 O(n) 行为。
在 R^3 中构造 Delaunay 曲面分割/Voronoi 复合体的良好增量算法具有 O(n^2) 的最坏情况运行时间(其中 n 为点数)。众所周知，这些最坏的情况在实践中很少发生，并且预计大多数“真实”情况会表现出准 O(n) 缩放。
Triangulation_3 的文档CGAL 中可用的类(class)包括对此类行为的讨论，以及指向某些论文的链接，这些论文提供了某些点分布的渐近复杂性的界限。
简而言之，增量 Delaunay 算法的运行时间基于几个不同的因素:(a) 用于插入单个点的内核的复杂性(通过修改局部拓扑) , (b) 用于定位要修改的镶嵌分割子集的搜索算法的复杂性，以及 (c) 点分布的“结构”被添加，以及它们被处理的顺序。
(a) 和 (b)(即 Bowyer-Watson 等)的“快速”算法是已知的，(c) 适合“有偏见的”准随机排序策略。在大多数实际情况下，这些技术的组合通常会导致 O(n) 行为。
这只会留下一组相当病态的案例，在这些案例中观察到的性能较差。对我来说，这些案例通常看起来非常具体，以至于它们基本上需要手工构建。
关于algorithm - 顺序构建 3D Voronoi-Delaunay 图的最佳时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56678930/