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/
See also this question: Position points and line
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.