我正在尝试了解DeWall算法的特定方法来执行 2D/3D delaunay 三角剖分/四面体化 (DT)。我对 3D 案例特别感兴趣。在其他分治算法创建部分 DT 并将它们合并在一起的情况下，DeWall 算法直接沿着分层切割构建 DT ：
但是，我在构建第一个单纯形的一开始就被困住了。在Cignoni 1997 - DeWall: A Fast Divide & Conquer Delaunay Triangulation Algorithm in Eᵈ</a> 作者写道
MakeFirstSimplex 选择离平面 α 最近的点 p₁ ∈ P。然后它选择第二个点 p2，使得 p2 是在 α 的另一侧离 p1 最近的点。然后，它搜索点 p3，使得围绕 1 面 (p1, p2) 的外接圆和点 p3 具有最小半径；(p1 ; p2; p3) 因此是 Σ 的 2 面。该过程继续进行，直到构建所需的 d-单纯形。
但是，如果我理解正确，这个过程应该总是导致一个确实属于 DT 的单纯形，但是当我用不同的点集测试它时，有时似乎会选择不属于 DT 的边。
我通过将（绿色）每个点（橙色）连接到其左右最近的邻居来测试这一点。还显示了使用三角形程序（灰色）和局部左右分割平面（黑色）制作的 DT 。
在上面放大的图片中，绿色边缘是由该程序挑选的，但其中一个不是灰色 DT 的一部分。因此，在类似的情况下，最高点的平面 α 会在该点的右侧，而 α 将是 DeWall 算法的剖切面，这将导致错误的单纯形。
众所周知，最近邻图始终是 DT 的一部分，但这对我们的情况没有帮助，因为不能保证切面 α 总是穿过其中之一。
有没有解释为什么这首先应该起作用，一些技巧或替代结构来获得那个受约束位置的第一个单纯形？