Bowyer-Watson algorithm for Delaunay triangulation fails, when three vertices approach a line.

Question

Bowyer-Watson algorithm as described on Wikipedia (https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm) doesn't generate any triangles for this valid point list:

p0 = (50, 50), p1 = (150, 50), p2 = (250, 67)

super-triangle is chosen to be:

p3 = (0,0), p4 = (1600,0), p5 = (0, 1200)

When point p2 is inserted, it is exactly outside triangle (p0,p1,p5), so it is not a bad triangle. Therefor it is not removed, and edge (p0,p1) is not part of the polygonal hole and triangle (p0,p1,p2) is thus never created.

If I choose a larger super-triangle it works, but then when p2 moves closer to the line defined by p0 and p1, the same happens.

Is Bowyer-Watson broken by design, or am I doing something wrong?

Answer 1

I think I know what you are after. The pseudo code on Wikipedia just specifies that the initial super triangle should contain all points in its interior. I could not pin down a corresponding statement in Bowyer's original work, but at least Watson's article states explicitly

Starting with $n+1$ arbitrary points, known to form an $n$-simplex whose convex hull contains the whole data set, [...]

And while both authors discuss degeneracies in general, it seems that one should rather demand that the vertices of the super triangle (or more generally: simplex) have to be outside all circumcircles of any three given points to begin with (which is hard when any three points are almost collinear). Then again, such a constellation is problematic only if it survives until all points have been treated.

How to solve? Personally, I would use symbolic vertices $(-\infty,-\infty)$, $(0,\infty)$, $(\infty,0)$ as super triangle. One then has to contemplate how to define the circumscribed circle of three vertices when some are infinite (spoiler: the disk becomes a half plane).