Delaunay triangulations and voronoi computation — Examples

The unperturbed heights are $0,1,2,1$. Each is $x+y$ at its site, so the four lifted points lie in the plane $z=x+y$.

All four original sites lie on the circle centered at $(1\mathrm{/}2,1\mathrm{/}2)$ with radius squared $1\mathrm{/}2$. No other sites are present, so neither selected triangle has a site strictly inside its circumdisk. They are weakly empty by [F4].

With the perturbation from [F2], the plane through $A,B,C$ has value $1+\epsilon -{\epsilon }^2+{\epsilon }^4$ at $D$, while $D$'s lifted height is $1+{\epsilon }^8$. Their difference is ${\epsilon }^8-\epsilon +{\epsilon }^2-{\epsilon }^4$, whose least nonzero exponent is $1$ with coefficient $-1$. Thus $D$ lies formally below the plane through $A,B,C$, and diagonal $AC$ is illegal. The flip selects $BD$ by [F3].

The plane through $A,B,D$ has value $2+{\epsilon }^2+{\epsilon }^8-\epsilon$ at $C$; subtracting from $C$'s height $2+{\epsilon }^4$ gives $\epsilon -{\epsilon }^2+{\epsilon }^4-{\epsilon }^8$, which is formally positive. The plane through $B,C,D$ has value ${\epsilon }^8-{\epsilon }^4+{\epsilon }^2$ at $A$; subtracting from $A$'s height $\epsilon$ gives $\epsilon -{\epsilon }^2+{\epsilon }^4-{\epsilon }^8$, also formally positive. Hence both $ABD$ and $BCD$ are lower triangles for the common lift.

When three synthetic identifiers are inserted below $1,2,3,4$, each input rank increases by three and each exponent $2^{r_i}$ is multiplied by $8$. Thus every input-only determinant polynomial becomes the four-site polynomial with $\epsilon$ replaced by ${\epsilon }^8$, which preserves the first nonzero coefficient sign. The augmented run therefore retains diagonal $BD$, and [F5] returns the stated weakly empty triangulation.

The two entries at $(1,0)$ form one unweighted duplicate class by [F1]. Their identifiers are $2$ and $3$, so the retained representative has id $2$ and id $3$ is recorded as discarded. The deduplicated coordinates are $(0,0),(1,0),(2,0)$.

These three distinct points lie on the horizontal line $y=0$ and are not all equal, so their affine dimension is exactly one. Sorting by $x$ gives the displayed order, and [F2] joins consecutive points, yielding edges $(0,0)(1,0)$ and $(1,0)(2,0)$.

The output has no triangles because the affine dimension is one; the algorithm therefore uses the branch of [F3], while the affine-dimension-two premise of [F4] does not apply.

Let ${\lambda }_0,{\lambda }_1,{\lambda }_2$ correspond to $(0,0),(2,0),(0,2)$. The coordinate equations give $2{\lambda }_1=1\mathrm{/}2$ and $2{\lambda }_2=1\mathrm{/}2$, hence ${\lambda }_1={\lambda }_2=1\mathrm{/}4$; their sum constraint gives ${\lambda }_0=1\mathrm{/}2$. All three are nonnegative, so the query lies in the triangle by [F3].

The interpolated value is $0\cdot {\lambda }_0+2\cdot {\lambda }_1+2\cdot {\lambda }_2=2(1\mathrm{/}4)+2(1\mathrm{/}4)=1$. Uniqueness follows from [F4].

The three sites are noncollinear, so by [F2] their convex hull is their single triangle. Its circumcircle has center $(1,1)$ and radius squared $2$; there are no other sites by [A1], so it is weakly empty, and [F5] returns this cell.