I am trying to understand a particular approach of the DeWall algorithm to perform a 2D/3D delaunay triangulation/tetrahedralization (DT). I am especially interested in the 3D case. Where other divide and conquer algorithms create partial DT and merge them together, the DeWall algorithm directly builds the DT along hierarchical cuts:
However, I am stuck at the very beginning of constructing the first simplex. In Cignoni 1997 - DeWall: A Fast Divide & Conquer Delaunay Triangulation Algorithm in Eᵈ the authors write
MakeFirstSimplex selects the point p₁ ∈ P nearest to the plane α. It then selects a second point p₂ such that p₂ is the nearest point to p₁ on the other side of α. Then, it searches the point p₃ such that the circum-circle around the 1-face (p₁, p₂) and the point p₃ has the minimum radius; (p₁ ; p₂; p₃) is therefore a 2-face of Σ. The process continues until the required d-simplex is built.
However, if I understand correctly this procedure should always lead to a simplex that does belong to the DT, but when I test this with different point sets, it seems to happen sometimes that an edge is picked which does not belong to the DT.
I've tested this by connecting (green) each point (orange) to its left and right nearest neighbour. A DT made with the triangle program (gray) and the local left-right-splitting-plane (black) are also shown.
In the zoomed-in picture above, the green edges are picked by that prodedure, but one is not part the gray DT. So in a similar case where the plane α of the topmost point would be a bit right of the point and α would be a cut-plane of the DeWall algorithm, this would lead to a wrong simplex.
It is known, that the nearest neighbour graph is always part of a DT, but that does not help in our case since is not guaranteed that a cut-plane α always crosses one of these.
Is there an explanation why this should work in the first place, some trick or an alternative construction to obtain the very first simplex at that constrained position?
