3 algorithm geometry time-complexity computational-geometry
我正在尝试实现以下 Bowyer-Watson 算法来实现 Delaunay 三角剖分。
function BowyerWatson (pointList)
// pointList is a set of coordinates defining the points to be triangulated
triangulation := empty triangle mesh data structure
add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
for each point in pointList do // add all the points one at a time to the triangulation
badTriangles := empty set
for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
if point is inside circumcircle of triangle
add triangle to badTriangles
polygon := empty set
for each triangle in badTriangles do // find the boundary of the polygonal hole
for each edge in triangle do
if edge is not shared by any other triangles in badTriangles
add edge to polygon
for each triangle in badTriangles do // remove them from the data structure
remove triangle from triangulation
for each edge in polygon do // re-triangulate the polygonal hole
newTri := form a triangle from edge to point
add newTri to triangulation
for each triangle in triangulation // done inserting points, now clean up
if triangle contains a vertex from original super-triangle
remove triangle from triangulation
return triangulation
该算法需要 O(N log N) 操作来对 N 个点进行三角测量，如所声称的那样。但是有没有办法根据上面的算法计算出来呢？我的意思是上述算法的哪一部分需要 log N 次，这会导致 n 个点的 (N log N) ？存在特殊的退化情况，如维基百科中所述，其达到 O(N2) 。这个堕落的案例有什么意义呢？
问题中的伪代码（维基百科文章中描述的 Bowyer/Watson 算法）为 O(n^2)。文章确实指出了这一点。维基百科的文章不太清楚 - 我认为实际上是错误的 - 关于需要做什么才能使算法 O(n log n) ，这样做并不是完全微不足道的。
当前的维基百科文章如下
可以通过多种方式提高效率。例如，三角形连通性可用于定位在其外接圆中包含新点的三角形，而不必检查所有三角形 - 通过这样做，我们可以将时间复杂度降低到 O(n log n)。
我认为仅使用“三角形连接”就可以实现 O(n log n) 行为。
在算法的每次迭代中需要做的就是给定一个新点 P，找到将 P 引入现有三角剖分将创建的“坏三角形”，这些三角形在其外接圆中包含 P。维基百科文章中提到的“三角形连通性”属性是，这些坏三角形将成为三角剖分邻接图中的一个连通分量，因此如果您碰巧知道一个这样的坏三角形，您可以通过执行图遍历轻松找到其他三角形仅限制于相邻的坏三角形。然而，前提是你有一个不好的三角形可以开始。一个明显的选择是包含 P 的三角形。
O(n log n) 时间复杂度主张的主要来源是“Efficient Unstructural Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm”，S. Rebay，1991，对这种情况的解释如下：（强调是我的）
算法效率取决于在每个点插入时搜索要删除的三角形的速度，并且通过了解每个三角形的相邻三角形，这会变得更加容易。事实上，由于所有要删除的三角形总是连续的，因此可以使用相邻三角形之间的树搜索来查找第一个三角形之后的所有其他要删除的三角形。在典型情况下，每次插入点时要删除的三角形的数量并不取决于所有现有三角形的数量。因此，如果与相邻三角形相关的信息可用，并且对要删除的第一个三角形进行 O(log N) 多维搜索，则该算法可以计算 O( N log N) 操作。然而，在特殊情况下，每次插入点时要删除的三角形数量可能非常大。在最坏的情况下，当每次插入点时必须删除所有现有三角形时，Bowyer-Watson 算法的操作次数会降低到 O(N^2)。
换句话说，如果维护三角形邻接图，并且有某种方法可以在 O(log n) 时间内找到包含任意点的三角形，那么 Bowyer-Watson 算法的复杂度为 O(n log n)，因为对于典型的三角剖分来说，坏的三角形分量非常小，我们可以认为它低于某个小常数。
维基百科、Rebay 等没有讨论使算法 O(n log n) 所需的“多维搜索”，但我可以从文献和其他方面提供三个建议：
将所有三角形的边界矩形存储在您选择的 2D 范围搜索数据结构中。例如，R 树或 R* 树。
使用 Delaunay 三角剖分本身的层次结构。维护三角剖分的历史，即三角形“级别”的树。我相信这就是 CGAL 的 Delaunay 实现的作用。
随机采样k个三角形，找到样本中距离目标点最近的三角形t ，对从t到包含目标点的三角形的邻接图进行A*搜索。这可能会表现良好，但形式上不是 O(log n)。