This flashcard is just one of a free flashcard set. See all flashcards!

Lift every vertex onto a parabola:


A circle in the plane maps to an ellipsoid on the parabola. This ellipsoid lies in a plane. Every point on the ground which lies inside the circle lifts to a point below the plane. Every point on the ground which lies outside the circle lifts to a point above the plane.

Suppose have a non-Delaunay pair of triangles , in the plane, where lies in 's circumcircle.
The lifted points lie in the same plane as the lifted ellipse of 's circumcircle. Since lies inside the circle, lies below the plane of . Thus, the edge is reflex.

By flipping the edge  to , we replace the reflex edge by the convex edge .

Note that the four points form a tetrahedron. Before the flip, our triangulation corresponded to the upward-facing faces of the tetrahedron. After the flip, it corresponded to the downward-facing faces of the tetrahedron.

Thus, with each flip, we monotonically decrease the height of our triangulation on the paraboloid. Tetrahedral edges which lie on the upward-facing side are never considered again. Thus, the algorithm terminates eventually.