Three fixes to Guibas and Stolfi's "Primitives for the Manipulation of
General Subdivisions and the Computation of Voronoi Diagrams":
One, their Locate primitive always works in the interior of the mesh,
but can get stuck in an infinite loop on the convex hull. Consider
this mesh:
y z
o-------o
/ \ / \
/ \ / \
/ \ / \
o--X----o-------o
u v w
Suppose you're trying to locate the X, which is collinear with uvw.
Look at p. 121 of Guibas & Stolfi. You are searching with an edge
e for the edge uv. Suppose that e := wv (directed toward v).
RightOf[X, e] is false. NOT RightOf[X, e.Onext] is true, so we
execute "e <- e.Onext", which sets e to wz. On the next iteration,
we execute "e <- e.Onext", which sets e back to wv. This continues
forever, an infinite loop.
To fix this bug, changing both "Not RightOf" expressions to "LeftOf"
expressions is a good start, but doesn't fulfill the criterion that
"Locate returns an edge e of the current Delaunay diagram such that
the given point X is either on e or _strictly_ inside the left face
of e." Rather, X might be on any edge of the left face; X might
even be the apex vertex. An explicit test for these possibilities
is necessary.
Two, I think there are other places in the paper where Guibas &
Stolfi sometime use RightOf when they mean NOT LeftOf, and vice
versa. Give careful consideration in each case to what should
happen when the determinant is zero.
Three, on p. 120, in their InsertSite procedure, the fifth-last line
is wrong. The statement "e <- t" should read "e <- e.Oprev".
If you're not using exact arithmetic for the CCW and InCircle tests,
other things can go wrong as well. Some problem cases can be
avoided by changing the code a bit, and some can't.