emptycircumcircle

emptycircumcircle is a term used in computational geometry to describe the empty circumcircle property of a triangulation of a finite set P of points in the plane. The property states that for every triangle in the triangulation, the circumcircle determined by its three vertices contains no other point of P in its interior. When this condition holds for all triangles, the triangulation is called a Delaunay triangulation.

The empty circumcircle property is central to Delaunay triangulations. Among all triangulations of a given point set, the Delaunay triangulation tends to avoid skinny triangles and, in general position, maximizes the minimum angle. It is also the planar dual of the Voronoi diagram.

Algorithmically, many triangulation methods are designed to enforce the empty circumcircle property. Incremental construction such as the Bowyer–Watson algorithm inserts points and retriangulates the set of triangles whose circumcircles contain the new point, while local edge flips are used to restore the criterion after changes.

In higher dimensions, the analogous condition uses circumspheres instead of circumcircles, yielding Delaunay tessellations. Degenerate cases occur when four or more points lie on a common circle (or sphere), in which case multiple Delaunay triangulations may exist, all satisfying the empty circumcircle property.

Applications of structures with the empty circumcircle property include mesh generation for finite element methods, computer graphics, and geographic information systems.