# Problem while constructing Delaunay triangulation

At the moment I'm implementing an algorithm to construct a Delaunay triangulation for a set of points. I'm using the algorithm described in Computational Geometry: Algorithms and Applications. The chapter on Delaunay triangulations is available from this link: http://www.cs.uu.nl/geobook/

I'm probably misunderstanding something in the algorithm, since I came across this problem:

I have four points $p_0(4,4)$, $p_1(0,0)$, $p_2(1,0)$ and $p_3(0,1)$. So I start the algorithm with the triangle $p_{-1}p_{-2}p_0$ and first add the point $p_1$.

For this step all the edges that need to be verified are legal, so we end up with the following triangles after this step: $p_{-1}p_{-2}p_1$, $p_{-1}p_1p_0$ and $p_1p_{-2}p_0$.

The next step is to add the point $p_2$ which is contained in $p_{-1}p_1p_0$. Again all edges are legal and we get the triangles: $p_{-1}p_{-2}p_1$, $p_1p_{-2}p_0$, $p_{-1}p_1p_2$, $p_{-1}p_2p_0$ and $p_2p_1p_0$.

Finally we add the point $p_3$ which is contained in $p_1p_{-2}p_0$. In the new triangle $p_1p_{-2}p_3$ the edge $p_1p_{-2}$ is illegal, and we should flip it with $p_3p_{-1}$. This edge however intersects $p_1p_0$.

Is there something wrong in my interpretation of illegal? Could someone give the different steps for this specific case, so I can see where I'm going wrong?

edit: here is an image illustrating things after $p_3$ is added, but before any of the edges have been legalized for that step.

Why is $p_1p_{-2}$ in the picture illegal? Triangle $p_{-2}p_1p_3$ looks like a valid Delaunay triangle to me (circle through these points is empty). You should flip $p_0p_1$ to $p_2p_3$ though.
• The edge $p_1p_{-2}$ is illegal, because in the cited source it says: if $\min(i,j,k,l)<0$ and $p_ip_j$ is not an edge of $p0p_{-1}p_{-2}$, then $p_ip_j$ is legal if and only if $\min(k, l) < \min(i, j)$. It is not the case that $-1 < -2$, so the edge $p_1p_{-2}$ is not legal. I can see that the other edge should be flipped, but I'm implementing the algorithm, so I need to find what is wrong in my interpretation. – bart_m8 Nov 26 '13 at 13:23
• I've checked my old copy of the book (2nd edition) I wrote some notes that the result can be non-planar; this is fixed if you remove the 'extra' points. In your case you could flip $p_1p_{-2}$. If you remove $p_{-2}$ and $p_{-1}$ at the end you still have a valid Delaunay triangulation. – Simon Nov 26 '13 at 20:52
• After insertion of $p_3$ you should also check $p_0p_1$ which is illegal. If you flip $p_0p_1$ also and you remove $p_{-1}$ and $p_{-2}$ at the end you've got the correct triangulation – Simon Nov 27 '13 at 9:55