Planar triangulations, Delaunay structures, and Voronoi cells

Use the unweighted deduplicated coordinate set of Finite indexed geometric site sets and duplicate handling. If its affine dimension is zero, its output is its single site. If its affine dimension is one, sort by the first varying coordinate (use $x$ if it varies, otherwise $y$) and take the chain joining consecutive sites; this is the lower-dimensional output and contains no triangles.

For affine dimension two, a triangulation of the sites is a finite family of nondegenerate closed triangles whose vertices are sites, whose union is the convex hull, and whose pairwise intersections are common faces. Its 1-skeleton is the graph with these sites as vertices and all triangle sides as edges; it is connected. The bounded faces of this plane graph are exactly the chosen triangles, and its one unbounded face is the exterior of the convex hull. The boundary edges of the convex hull are subdivided at every site on that boundary. A triangle is weakly empty-circle when no site lies strictly inside its circumdisk; other sites may lie on its boundary.

For each site $p$, its closed Voronoi cell is $V(p)=\{x\in {\mathbb{R}}^2:\mathrm{\parallel }x-p{\mathrm{\parallel }}^2\le \mathrm{\parallel }x-q{\mathrm{\parallel }}^2\text{ for every site }q\}\mathrm{.}$ A tie belongs to every minimizing cell. The Delaunay graph has one vertex for each site and an edge $pq$ exactly when $V(p)\cap V(q)$ contains a nontrivial line segment. A Voronoi vertex is a point belonging to at least three distinct cells. It is dual to the convex polygon of the nearest sites; A Voronoi vertex has a common empty circle of nearest sites proves that those sites are vertices on one empty circle centered at that point. A Delaunay triangulation is a triangulation refining these polygonal Delaunay faces and having weakly empty circumdisks. In a cocircular face the triangulation need not be unique; the chosen algorithmic refinement is the fixed-universe convention of Stable-id lexicographic lift perturbation for cocircular and power ties.

The convex-hull boundary is the boundary of the union of the triangles. An unbounded Voronoi cell corresponds to a site on that boundary. No minimum-angle or other mesh-quality condition is part of these definitions.