Delaunay triangulations and empty circles

Take three noncollinear sites in counterclockwise order. The determinant below is positive when a fourth site is inside their circumcircle, negative when outside, and zero on the circle. Reversing the triangle orientation reverses that interpretation, so a caller must either normalize the order or combine the sign with an orientation test. A zero is an exact cocircular event, not evidence of an arithmetic failure. Filtered evaluation must retain that zero or resolve an uncertain sign through a certified fallback.

The empty-circle property uses the open disk: other sites may lie on the circumference in a degenerate configuration. In general position this distinction disappears because four cocircular sites are excluded. A local edge flip in a convex quadrilateral replaces a diagonal when the opposite site violates the relevant empty-circle test. The convexity condition is essential; an arbitrary pair of incident triangles does not always admit a valid alternate diagonal. Degenerate flips require a consistent rule to avoid changing the structure indefinitely.

Lift each planar site to the paraboloid whose height is its squared norm. A circle becomes the intersection of that paraboloid with a plane. Sites outside the circle lift above that plane, while inside sites lift below it. Consequently an empty circumcircle corresponds to a lower supporting face of the lifted convex hull. Projecting lower triangular faces gives Delaunay triangles. Four cocircular sites lift to one coplanar face, explaining why a diagonal is not selected uniquely by the unperturbed geometry.

For a noncollinear set in general position, let the convex hull have h vertices. A triangulation with all n sites and no extra vertices has the edge and bounded-face counts below. These counts follow from Euler's formula and counting triangle-edge incidences, with hull edges counted once. They are useful structural checks but do not alone prove the empty-circle property. Delaunay also maximizes the smallest triangle angle among triangulations of the same sites, yet arbitrarily poor input spacing can still force very small angles.

Two Voronoi cells sharing an edge correspond to a Delaunay edge. In generic position, three meeting cells correspond to a triangle. When four cells meet at one Voronoi vertex, their dual feature is naturally a polygonal Delaunay face. A chosen triangulation adds a diagonal inside that face, although the corresponding two Voronoi cells need not share a positive-length edge. Calling every refinement edge a literal dual of an ordinary Voronoi edge would hide this distinction.

Robust triangulation therefore combines a combinatorial policy with arithmetic guarantees. Exact incircle and orientation decisions address which represented sites satisfy the predicates. Constructing centers, clipping triangles, or introducing Steiner points may require stronger coordinate representations. A perturbation policy should be fixed independently of insertion order when an incremental algorithm relies on a canonical structure for each subset. Testing on a square is a useful tie case, rather than a reason to assume the uniqueness theorem applies without its general-position hypotheses.