Delaunay triangulations and voronoi computation

Suppose the positive canonical integers $N=\{n\cdot 1_F:n\ge 1\}$ were bounded above by some $y\in F$. By [A1], let $s=\sup N$. Since $1_F>0$, $s-1_F<s$, so $s-1_F$ is not an upper bound; choose $m\ge 1$ with $m\cdot 1_F>s-1_F$.

Adding $1_F$ gives $(m+1)\cdot 1_F>s$, while $(m+1)\cdot 1_F\in N$ and $s$ is an upper bound of $N$. This contradiction proves that $N$ is unbounded above.

Suppose no canonical integer exceeds $x$. Then every positive canonical integer is at most $x$, making $N$ bounded above, contrary to step 2.1. Thus some canonical integer exceeds $x$.

The displayed expression has degree at most one. Substitution gives $P(a)=y_0$ and $P(b)=y_0+(y_1-y_0)=y_1$.

Write any degree-at-most-one interpolant as $Q(X)=\alpha +\beta X$. Its two value equations imply $\beta (b-a)=y_1-y_0$, so $\beta =(y_1-y_0)\mathrm{/}(b-a)$; then $\alpha =y_0-\beta a$. These coefficients are uniquely determined and give exactly the polynomial in step 1.1.

Put $h_i=\mathrm{\parallel }{p}_i{\mathrm{\parallel }}^2-w_i$. Let $A$ be the $d\times d$ matrix whose rows are $p_i-p_0$ for $i=1,\dots ,d$. Subtract row $p_0$ from each other row of the orientation matrix defining $O_d$, then expand along its final column. Since the base points are affinely independent, $\det A\mathrm{\ne }0$, and the cofactor sign gives $\det A=(-1{)}^d{O}_d$.

Expanding the equal power-sphere equations in [A1] gives $h_i-h_0=2c\cdot (p_i-p_0)$ for $1\le i\le d$. For the query row, the same expansion gives $h_q-h_0=2c\cdot (q-p_0)+\mathrm{\Delta }(q)$.

In the lifted determinant defining $P_d$, subtract row $p_0$ from all other rows and expand along the final column. The cofactor sign is $(-1{)}^{d+3}$. Subtract $2c_j$ times coordinate column $j$ from the lifted-height column for every $j$; by [step 1.2] the first $d$ height entries become zero and the query height entry becomes $\mathrm{\Delta }(q)$. The remaining determinant is $\det A\mathrm{\Delta }(q)$, so $P_d=(-1{)}^{d+3}\det A\mathrm{\Delta }(q)=-O_d\mathrm{\Delta }(q)$ by [step 1.1].

Multiplying the identity in [step 2.1] by $O_d$ gives $O_d{P}_d=-O_d^2\mathrm{\Delta }(q)$. Since affine independence gives $O_d\mathrm{\ne }0$, the factor $O_d^2$ is positive; hence the product has the claimed inside/on/outside sign.

Choose three distinct sites $p_1,p_2,p_3$ whose cells contain $x$. From $x\in V(p_i)$, $\mathrm{\parallel }x-p_i{\mathrm{\parallel }}^2\le \mathrm{\parallel }x-p_j{\mathrm{\parallel }}^2$ for every $j$; reversing $i,j$ gives equality. Thus all sites whose cells contain $x$ have the same squared distance $r^2$ from $x$. For every other site $q$, the defining inequality gives $r^2\le \mathrm{\parallel }x-q{\mathrm{\parallel }}^2$, so none is strictly inside the circle.

The common radius is positive, since radius zero would force every site whose cell contains $x$ to equal $x$, contradicting distinctness and the existence of three sites. A line intersects the circle $\mathrm{\parallel }y-x{\mathrm{\parallel }}^2=r^2$ in at most two points: parameterizing the line as $y=a+tv$ gives a nonzero quadratic equation in $t$. Hence no three of the sites on the circle are collinear. For any one such site $p$, the tangent line at $p$ supports the disk and meets the circle only at $p$; therefore $p$ cannot be a convex combination of the other circle sites. All nearest sites are extreme points of their convex hull, so that hull is a polygon with these sites as its vertices.

Expand the determinant polynomial in [F3] along its lifted-height column. It has constant coefficient equal to the original determinant and one perturbation term for each row; the coefficient of the query row's perturbation is its cofactor, which is $O_d$ up to sign. By [A1] this coefficient is nonzero, so the polynomial is not identically zero.

The exponents $2^{r_i}$ are distinct because the ranks in [F3] are distinct across the fixed universe [F1]. Thus no two perturbation terms have the same exponent and their nonzero coefficients cannot cancel. The sign selected by the procedure is exactly the sign of the first nonzero coefficient in this one polynomial, so it is a well-defined sign of one common lifted tuple, not a separate choice for each predicate.

If the original determinant is nonzero, its constant coefficient is the unique term of exponent $0$, while all perturbation exponents are positive; therefore the first nonzero coefficient is the original determinant and its sign is unchanged. If the original determinant is zero, step 1.1 shows a nonzero tie polynomial and step 2.1 gives its unique first coefficient. The finite set $U$ supplies one fixed rank assignment for every tuple, so the signs are coherent and the procedure uses no arbitrary epsilon choice.

Let $h$ be the number of hull corners, meaning the boundary sites that are not in the relative interior of any hull edge. Their interior angles sum to $(h-2)\pi$, because a convex $h$-gon is divided into $h-2$ triangles by diagonals from one corner. Each of the other $k-h$ boundary sites has straight angle $\pi$. Around each interior site the incident triangle angles sum to $2\pi$, while at each boundary site they sum to its hull angle. Counting all triangle angles gives $\pi T=2\pi (n-k)+(h-2)\pi +(k-h)\pi =(2n-k-2)\pi$, hence $T=2n-2-k$.

Count incidences between triangle sides and edges. Each triangle contributes three. An interior edge has one triangle on each of its two local sides; a hull edge has exactly one incident triangle inside the convex hull. Since the hull boundary has $k$ sites, it has $k$ subdivided boundary edges. Thus $3T=2(E-k)+k=2E-k$.

Substituting the value of $T$ from step 1.1 into step 1.2 gives $E=3n-3-k$. Consequently $n-E+T=n-(3n-3-k)+(2n-2-k)=1$, proving both identities.

For each noncollinear triple $(a,b,c)$ from $P$, its center $o$ is uniquely determined by $2o\cdot (b-a)=\mathrm{\parallel }b{\mathrm{\parallel }}^2-\mathrm{\parallel }a{\mathrm{\parallel }}^2,2o\cdot (c-a)=\mathrm{\parallel }c{\mathrm{\parallel }}^2-\mathrm{\parallel }a{\mathrm{\parallel }}^2\mathrm{.}$ The coefficient matrix has nonzero determinant because $a,b,c$ are noncollinear, so this system has a unique real solution; put $r^2=\mathrm{\parallel }o-a{\mathrm{\parallel }}^2$. There are finitely many such triples.

Let $B$ be the maximum of $1$, the absolute values of all input coordinates, the absolute values of all center coordinates from step 1.1, and all corresponding values $r^2$. This is a finite maximum in the total order of $\mathbb{R}$. By [F3], choose an integer $M>B$.

Take baseline vertices $v_1=(-8M,-4M)$, $v_2=(8M,-4M)$, and $v_3=(0,8M)$. At height $y\in [-M,M]$, their triangle has horizontal half-width $\frac{2}{3}(8M-y)\ge \frac{14}{3}M>M$. Since every input site has $\mathrm{\mid }x\mathrm{\mid },\mathrm{\mid }y\mathrm{\mid }<M$, all sites lie strictly inside this triangle.

Step 2.1 gives $\mathrm{\mid }{o}_1\mathrm{\mid },\mathrm{\mid }{o}_2\mathrm{\mid }<M$ and $r^2<M$, while $M>1$. For either lower baseline vertex $v_1=(-8M,-4M)$ or $v_2=(8M,-4M)$, $\mathrm{\parallel }{v}_i{\mathrm{\parallel }}^2=80M^2$ and $\mathrm{\mid }{v}_i\cdot o\mathrm{\mid }<12M^2$, so $\mathrm{\parallel }{v}_i-o{\mathrm{\parallel }}^2=\mathrm{\parallel }{v}_i{\mathrm{\parallel }}^2-2v_i\cdot o+\mathrm{\parallel }o{\mathrm{\parallel }}^2>56M^2>M>r^2\mathrm{.}$ For the top vertex $v_3=(0,8M)$, $\mathrm{\parallel }{v}_3{\mathrm{\parallel }}^2=64M^2$ and $\mathrm{\mid }{v}_3\cdot o\mathrm{\mid }<8M^2$, giving $\mathrm{\parallel }{v}_3-o{\mathrm{\parallel }}^2>48M^2>M>r^2$. Thus each vertex is strictly outside every candidate circle, using only squared distances. The input containment and all circle exclusions have positive margins.

The strict site-containment, strict circle-exclusion, and nonzero orientation of the supertriangle persist under sufficiently small changes in its three baseline vertices, because they are finitely many strict inequalities in continuous polynomial or squared-distance expressions. Choose open disks $U_1,U_2,U_3$ about the baseline vertices small enough to preserve these conditions for every choice $v_i\in U_i$.

Dyadic rationals are dense: for $a<b$, use [F3] to choose an integer $N>1\mathrm{/}(b-a)$, then choose $k>N$; induction gives $2^k\ge k+1>N$, hence $2^{-k}<b-a$. The least integer $m>2^{k}a$ exists by the Archimedean property and the well-ordering of the naturals after translating by an integer lower bound; minimality gives $m\le 2^{k}a+1<2^{k}b$, so $m{2}^{-k}\in (a,b)$. Hence dyadic points are dense in every open disk: place an open rectangle inside the disk, choose a dyadic first coordinate away from the finitely many vertical lines among the forbidden set, and then choose a dyadic second coordinate away from the finitely many intersections with that vertical line. If [A1] holds, choose $v_1\in U_1$ outside the finitely many lines through pairs and circles through triples of input sites. Next choose $v_2\in U_2$ outside all lines through pairs and circles through noncollinear triples of $P\cup \{v_1\}$, and choose $v_3\in U_3$ outside those determined by pairs and triples of $P\cup \{v_1,v_2\}$. A finite union of such lines and circles cannot contain an open disk by the rectangle argument. These choices make the augmented set have no collinear triple or cocircular quadruple. Without [A1], any dyadic choices in the disks still satisfy the first part.

The selected vertices are dyadic, preserve strict containment and exclusion by [step 4.1], and satisfy the additional general-position properties by [step 5.1]. This proves both claims.

The two interpolants agree at the four boundary vertices. Their common diagonal intersection $O$ lies strictly inside both diagonals. On the four triangles formed by $O$ and the four boundary edges, each interpolant is affine; their difference is zero at the two boundary endpoints and equals $\delta :=g_{BD}(O)-g_{AC}(O)$ at $O$.

Write $O=(1-t)B+tD$ with $0<t<1$. The plane through $A,B,C$ agrees with $g_{AC}$ at $O$ because $O\in AC$, and its value at $B$ equals the lifted height of $B$. By [A1] its value at $D$ is strictly larger than the lifted height of $D$. Affinity along $BD$ therefore gives $g_{AC}(O)>g_{BD}(O)$, so $\delta <0$.

On a triangle, the integral of an affine function is its area times the average of its three vertex values; this follows by mapping to the reference triangle, where each barycentric coordinate has integral one third of its area. Thus each of the four overlay triangles contributes its area times $\delta \mathrm{/}3$ to the integral of $g_{BD}-g_{AC}$. Their areas sum to the quadrilateral area, so the total difference is $\mathrm{area}(ABCD)\delta \mathrm{/}3<0$.

The row-subtraction and height-column elimination used in [F2] are polynomial determinant identities in the site heights, so they remain valid coefficientwise after each height is replaced by its formal perturbation. Writing ${\mathrm{\Delta }}_D$ for the query height minus that plane's height at $D$ and $O$ for the base orientation determinant, the identity is $OP=-O^2{\mathrm{\Delta }}_D$. The normalized determinant therefore has the opposite sign to ${\mathrm{\Delta }}_D$, so the strict below-plane condition gives a positive, illegal sign. By [F3]–[F4], one common formal configuration resolves a zero constant term. Thus the below-plane condition is exactly the illegal incircle sign and its flip strictly decreases the potential.

Fix $x\in \mathrm{conv}(P)$. A feasible representation is a vector $({\lambda }_i{)}_{i\in P}$ with ${\lambda }_i\ge 0$, ${\sum }_i{\lambda }_i=1$, and ${\sum }_i{\lambda }_i{p}_i=x$. Its formal height is $H(\lambda )={\sum }_i{\lambda }_i{h}_i$. If its support has more than $d+1$ sites, the vectors $(p_i,1)\in {\mathbb{R}}^{d+1}$ are linearly dependent, so there is a nonzero vector $({\alpha }_i)$ on that support with ${\sum }_i{\alpha }_i=0$ and ${\sum }_i{\alpha }_i{p}_i=0$. Such a vector has both positive and negative entries. Choose one of the two directions $\lambda +t\alpha$ that does not increase $H$ and increase $\mathrm{\mid }t\mathrm{\mid }$ until a coefficient first becomes zero. This preserves feasibility and reduces support. Repeating finitely gives a feasible representation of support at most $d+1$ with no greater height.

There are finitely many supports of size at most $d+1$. For any affinely independent support, its coefficients representing $x$ are unique; any dependent support reduces by step 1.1. Therefore the minimum formal height among feasible representations is attained among a finite nonempty set of basic supports.

Exclude temporarily the finite union of convex hulls of subsets of at most $d$ sites. For an $x$ outside this union, choose a minimizing support of smallest cardinality; it has exactly $d+1$ sites, is affinely independent, and has strictly positive coefficients ${\lambda }_i$. Indeed, a dependent support reduces by step 1.1 without increasing its minimal height, contradicting minimal cardinality. For any other site $q$, write its unique affine coordinates $q={\sum }_i{\alpha }_i{p}_i$, ${\sum }_i{\alpha }_i=1$. For sufficiently small positive $t$, replacing ${\lambda }_i$ by ${\lambda }_i-t{\alpha }_i$ and adding coefficient $t$ at $q$ remains feasible. Minimality gives $h_q-{\sum }_i{\alpha }_i{h}_i\ge 0$. Hence the hyperplane through the lifted support sites lies below every lifted site and its projected simplex contains $x$.

The set excluded in step 3.1 lies in a finite union of proper affine subspaces. A line segment in any open ball of $\mathrm{int}\mathrm{conv}(P)$ can be chosen in a direction not parallel to any of these subspaces; each subspace then removes at most one point of the segment. Thus the complement is dense in the interior. The interior is dense in the whole convex hull: join any hull point to a fixed interior point, and every point of the joining segment other than the hull endpoint is interior by convexity. There are finitely many $d$-tuples of sites, hence finitely many lower simplices; their projected simplices are closed. Step 3.1 puts a dense subset of $\mathrm{conv}(P)$ in their union, so that finite union covers the entire convex hull.

If a lower hyperplane contained at least $d+2$ lifted sites, its projected face would contain a nondegenerate $d$-tuple and an additional site, contradicting the nonzero determinant from [F3]. Thus every full-dimensional lower cell is a simplex. If two projected lower simplices have support planes $L_1,L_2$, all their vertices lie on or above both supporting planes. For a point $x$ in the intersection of their projections, the two lifted convex combinations at $x$ therefore force $L_1(x)\ge L_2(x)$ and $L_2(x)\ge L_1(x)$; hence $L_1(x)=L_2(x)$. On each simplex the corresponding plane difference has one sign at every vertex, so its zero set is a face. If $L_1=L_2$, the nonzero determinant [F3] forces the same $d+1$ vertices. Thus intersections are common faces.

The supporting inequality for a formal lift has nonnegative constant-term difference at each site; otherwise its negative constant coefficient would force a negative formal sign by [F3]. The constant terms therefore give the unperturbed weak support inequalities, and [F4] identifies them with empty power spheres.

Fix a vertex $v$ of $Q$ and let $C$ be the convex hull of its other vertices. Since $v$ is extreme, $v\mathrm{\notin }C$. Writing $C$ as the continuous image of the compact coefficient simplex shows that $C$ is compact, so choose $q\in C$ minimizing $\mathrm{\parallel }v-q\mathrm{\parallel }$. For every $y\in C$ and $0<t\le 1$, $q+t(y-q)\in C$, hence $\mathrm{\parallel }v-q-t(y-q){\mathrm{\parallel }}^2\ge \mathrm{\parallel }v-q{\mathrm{\parallel }}^2$. Expanding, dividing by $t$, and letting $t\downarrow 0$ gives $(v-q)\cdot (y-q)\le 0$. Therefore $\mathrm{\ell }(x)=(v-q)\cdot x$ satisfies $\mathrm{\ell }(v)-\mathrm{\ell }(y)\ge \mathrm{\parallel }v-q{\mathrm{\parallel }}^2>0$ for every $y\in C$. Choose $\delta >0$ smaller than every gap $g_u=\mathrm{\ell }(v)-\mathrm{\ell }(u)>0$ over the other vertices. The section $Q_v=Q\cap \{\mathrm{\ell }=\mathrm{\ell }(v)-\delta \}$ is a cross-section of the cone generated by the directions $u-v$. Indeed, the segment $[v,u]$ meets it at $x_u=v+\frac{\delta }{g_u}(u-v)$, and if $x={\lambda }_{v}v+{\sum }_{u\mathrm{\ne }v}{\lambda }_{u}u\in Q_v$, then ${\mu }_u={\lambda }_u{g}_u\mathrm{/}\delta$ are nonnegative, sum to $1$, and give $x={\sum }_{u\mathrm{\ne }v}{\mu }_u{x}_u$. Thus $Q_v=\mathrm{conv}\{x_u:u\mathrm{\ne }v\}$. The cone is four-dimensional because the vertex differences span ${\mathbb{R}}^4$, so its transverse section is three-dimensional. A face of this cone is generated by the directions of the corresponding face of $Q$ through $v$: a supporting linear inequality of the cone restricts to a supporting inequality of $Q$ tight at $v$, and conversely the facets active at $v$ define the cone. Therefore its extreme rays correspond to edges at $v$, and its three-dimensional faces correspond to facets of $Q$ containing $v$. A facet of $Q$ not containing $v$ misses the section because all its vertices lie below the section level. Intersecting cone faces with the transverse section lowers dimension by one, so the vertices of $Q_v$ correspond to edges of $Q$ at $v$ and its facets correspond to facets of $Q$ containing $v$. Write $d_v,t_v$ for the numbers of vertices and facets of $Q_v$.

Choose a facet $F_0$ of $Q_v$. A viewpoint just outside a relative-interior point of $F_0$ gives a Schlegel projection onto its plane: each ray through an interior point of $F_0$ enters $Q_v$ there and, by convexity and boundedness, has a unique exit point on the opposite boundary. The set of such viewpoints contains an open region. The exit points cover $F_0$; uniqueness makes projected facet interiors disjoint, and shared edges project to shared boundaries. Choose the viewpoint generically within this region so projected vertices are distinct and no three projected vertices are collinear. A pair coincidence forces the viewpoint onto the line through that pair; collinearity of three projected vertices forces it into the plane through those three noncollinear vertices. These finitely many proper algebraic sets cannot exhaust an open region: each lies in the zero set of a nonzero polynomial, and a nonzero polynomial cannot vanish on an open set (in one variable it has finitely many roots; induction on the variables applied to its coefficient polynomials proves the claim). Triangulate each projected convex polygonal facet by joining one vertex to its nonadjacent vertices. This yields a triangulation of $F_0$ with $d_v$ sites and $k_v$ hull sites, where $k_v$ is the number of vertices of $F_0$ and $k_v\ge 3$.

There are $t_v-1$ bounded facets in the Schlegel triangulation, and each contributes at least one triangle, so $t_v-1\le T_v$. By [F1], $T_v=2d_v-2-k_v$. Therefore $t_v\le 2d_v-1-k_v\le 2d_v-4$.

Count vertex-facet incidences. Every facet of a four-dimensional polytope has at least four vertices, so $4f_3\le {\sum }_v{t}_v$. By step 3.1 and the fact that each edge has two endpoints, ${\sum }_v{t}_v\le 2{\sum }_v{d}_v-4m=4f_1-4m$.

The graph of $Q$ is simple, so $f_1\le \left(\genfrac{}{}{0px}{}{m}{2}\right)$. Step 4.1 yields $4f_3\le 4f_1-4m$, hence $f_3\le f_1-m\le \left(\genfrac{}{}{0px}{}{m}{2}\right)-m=m(m-3)\mathrm{/}2$.

The matrix with columns $p_1-p_0,p_2-p_0$ is invertible by [A1], so the two coordinate equations uniquely determine ${\lambda }_1,{\lambda }_2$ and then ${\lambda }_0=1-{\lambda }_1-{\lambda }_2$. Thus the coordinates in [F1] are unique, and their nonnegativity is exactly membership in the convex combinations defining the triangle.

Parameterize an edge by $x(t)=(1-t)p_0+t{p}_1$. Its barycentric interpolant is $(1-t)f_0+t{f}_1$. Apply [F3] with nodes $0,1$ and data $f_0,f_1$: the unique cardinal polynomial is $f_0+(f_1-f_0)t$, which equals the edge interpolant, including its separate endpoint values.

Each ${\lambda }_i(x)$ is affine in $x$, so $I_{T}f={\sum }_i{\lambda }_i{f}_i$ is affine and has value $f_i$ at vertex $p_i$. An affine function agreeing at three noncollinear vertices is unique because its three coefficients are determined by an invertible $3\times 3$ augmented vertex matrix. On a shared edge, both triangle restrictions are affine in the edge parameter and agree at its two endpoints, so they coincide throughout the edge; the same endpoint argument handles a shared vertex.

A nonempty finite set of real distances $\{\mathrm{\parallel }x-p{\mathrm{\parallel }}^2:p\in P\}$ has a minimum. The finite set of identifiers attaining it has a least element, so the specified query returns exactly one minimizing site. Its inside/outside status is decided by the defining convex-hull membership test, equivalently by triangle barycentric membership when $x$ lies in the triangulated hull; outside the hull no triangle is returned but the same finite minimum still exists.

By [F1] and [A1], the triangulation has $k$ hull boundary sites and therefore exactly $k$ subdivided hull edges. Then [F2] gives $T=2n-2-k$.

By [F2], $E=3n-3-k$. Since $k\ge 3$, the formulas imply $T<2n$ and $E<3n$.

Consider any triangulation of a convex polygon whose interior edges all have the legal lifted incircle sign. The determinant identity [F2] is polynomial in the height entries, so it remains true coefficientwise for the formal heights [F3]; exact signs are supplied by [F5]. Across a shared edge the affine triangle planes agree on the edge. The legal sign says the opposite vertex of either triangle lies on or above the continuation of the other plane; the two tests are equivalent because the difference of the planes vanishes on the shared edge and changes sign across it. Thus the piecewise-affine height has nondecreasing slope when crossing the edge. For any triangle $\tau$ and any vertex $q$, choose $x$ in the interior of $\tau$ so $xq$ crosses edges transversely and avoids every other vertex; finitely many lines are forbidden. Along $xq$ the slope is nondecreasing, so the height at $q$ is at least the value of the plane through $\tau$ there. Every triangle plane therefore supports all lifted vertices from below; taking constant terms gives weakly empty original circumdisks.

In ordinary mode, CHOOSE-SUPERTRIANGLE(P,0) enumerates finitely many dyadic triples at each height and performs finitely many exact tests on each. [F1] guarantees an admissible candidate, so some finite height contains one and this search terminates; [F5] supplies terminating exact tests. The initial supertriangle is a triangulation and has no interior edge, so its edges are vacuously legal. Each input site lies strictly inside it by [F1]. The batch algorithm calls INSERT(p,none), whose exact locator scans the finite current triangle list and tests each triangle with finitely many orientation predicates; [F5] makes every test terminate. Because the current triangles cover the supertriangle, the scan finds a containing face or an interior edge. Duplicate collapse excludes an existing vertex, and strict containment excludes a hull edge, so these are the only cases. An edge incidence lookup supplies the two faces of an interior edge. A supplied face or edge certificate is checked with the same exact predicates by the update procedure, without a scan; an invalid certificate returns its stated status. Splitting a face replaces it by three nondegenerate triangles covering it. Splitting an interior edge at its strict interior point replaces its two incident faces by four nondegenerate triangles covering their union. Both operations preserve a nonoverlapping triangulation.

Let $uvw$ be any current lower triangle with plane $z=2o\cdot x+b$ over the formal field and set $c=\mathrm{\parallel }o{\mathrm{\parallel }}^2+b$. Its constant plane is the ordinary paraboloid plane through $u,v,w$, because the projected base is nondegenerate. Define the formal power distance ${\pi }_q(x)=\mathrm{\parallel }x-q{\mathrm{\parallel }}^2+{\epsilon }^{2^{r_q}}$ using the fixed height perturbation. Then ${\pi }_u(o)={\pi }_v(o)={\pi }_w(o)=c$ and every current site $q$ has ${\pi }_q(o)\ge c$ by the supporting-plane inequality. Suppose a new site $p\mathrm{\ne }v$ lies formally below this plane. This holds at a split because a nonvertex point of triangle $uvw$ is strictly inside its unperturbed circumdisk, so the constant term of ${\pi }_p(o)-c$ is negative; it also holds for a flip-conflict triangle by the illegal test. At $x=v$, ${\pi }_p(v)-{\pi }_v(v)=\mathrm{\parallel }p-v{\mathrm{\parallel }}^2+{\epsilon }^{2^{r_p}}-{\epsilon }^{2^{r_v}}$ has positive constant term. The difference ${\pi }_p-{\pi }_v$ is affine in $x$, so along the segment from $o$ to $v$ it has a zero at some formal parameter $0<t<1$. At that point $x_{\ast }$, for every other current site $q$, the affine difference ${\pi }_q-{\pi }_v$ is nonnegative at $o$ and strictly positive at $v$ (its constant term there is $\mathrm{\parallel }q-v{\mathrm{\parallel }}^2>0$), hence strictly positive at $x_{\ast }$. Therefore $p,v$ are strict nearest sites for the finite formal power diagram. The strict inequalities persist on a nontrivial segment of their formal bisector; each center there defines a supporting graph plane through the two lifts, so $pv$ is a lower-hull edge of the common lifted configuration.

Such a formal nearest-site edge is locally legal. After a rigid motion write $p=(0,0)$ and $v=(a,0)$. Their formal power bisector consists of centers $(b_0,t)$, where $b_0=(a^2+{\eta }_v-{\eta }_p)\mathrm{/}(2a)$ and ${\eta }_i={\epsilon }^{2^{r_i}}$. For opposite triangle vertices $u=(b,c)$ and $w=(d,e)$ with $c>0>e$, the power-distance inequalities for $p,v$ to be no farther than $u,w$ are $t\le t_u$ and $t\ge t_w$, where $t_u=(b^2+c^2-2b_{0}b+{\eta }_u-{\eta }_p)\mathrm{/}(2c)$ and $t_w=(d^2+e^2-2b_{0}d+{\eta }_w-{\eta }_p)\mathrm{/}(2e)$. These intervals intersect exactly when $t_w\le t_u$. The formal incircle determinant says $w$ lies below the plane through $p,v,u$ exactly when $t_w>t_u$, so the empty-bisector segment precludes an illegal sign. Conversely, if an edge opposite $p$ is illegal, [F2] puts $p$ inside or on the original circle through the adjacent triangle. To verify flippability, put the edge line at height $0$ with endpoints $a=(0,0),b=(1,0)$ and opposite vertices $w,p$ at heights $y_w>0>y_p$. If $p$ is inside the circle through $a,b,w$, the second intersection of line $pw$ with the circle lies beyond $p$ on the negative side, so the segment crosses height $0$ inside the disk. If $p$ is on the circle, $p,w$ are the two circle intersections and their segment has the same property. The disk meets height $0$ exactly in the chord $[a,b]$, so the crossing is inside that edge; the quadrilateral is strictly convex and the flip is valid. For a flip, the old non-$p$ triangle was lower before insertion and the illegal test puts $p$ formally below its plane; step 2.1 therefore supplies the new $p$-incident edge. Exact zero tests are resolved coherently by [F3] and evaluated by [F5].