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