Three-dimensional Delaunay and weighted regular triangulations by lifting

For a weighted site $(p,w)$, define its power distance from $x\in {\mathbb{R}}^3$ by ${\pi }_{(p,w)}(x)=\mathrm{\parallel }x-p{\mathrm{\parallel }}^2-w\mathrm{.}$ Its lifted point is $\widehat{p}=(p,\mathrm{\parallel }p{\mathrm{\parallel }}^2-w)\in {\mathbb{R}}^4$. A lower face of the lifted convex hull is a face supported by a nonvertical hyperplane $z=\mathrm{\ell }(x)$ with every lifted site on or above that hyperplane. The projection of the union of lower faces is the regular subdivision of the projected sites; a simplex in that subdivision has an empty power sphere, meaning its common power distance is no larger than that of any input site.

The lex-refined lift is interpreted over the ordered rational-function field of Stable-id lexicographic lift perturbation for cocircular and power ties, using one fixed finite universe of all input sites. When every weight is zero, the regular subdivision is the ordinary 3D Delaunay subdivision and power spheres are circumspheres. A weighted site is original-hidden if its unperturbed lift is not a vertex of any lower face of the original lifted convex hull, and formal-hidden if its lex-refined lift is not a vertex of any lower face of the fixed formal lifted convex hull. These notions can differ; the algorithm's hidden report means formal-hidden. A nonsimplicial lower face is refined with the same fixed-universe lexicographic lift convention. For projected affine dimension below three, the algorithm reports lower-dimensional with that dimension and the exact deduplicated site list, and makes no tetrahedralization claim. A tetrahedral output is claimed only on the full-dimensional branch with nondegenerate projected bases.