Three-dimensional Delaunay and regular output size is quadratic

Assume $n\ge 5$. For each five-site tuple whose projected points contain four affinely independent sites, order four such sites first and the fifth last, and let $P(\epsilon )$ be its lifted determinant polynomial. By [F2], this polynomial is nonzero. Write it as $c{\epsilon }^k+{\sum }_j{c}_j{\epsilon }^{k_j}$, where $c\mathrm{\ne }0$ and every $k_j>k$. If $C={\sum }_j\mathrm{\mid }{c}_j\mathrm{\mid }>0$, then for $0<\epsilon <\min (1,\mathrm{\mid }c\mathrm{\mid }\mathrm{/}(2C))$, the absolute value of the higher terms after dividing by ${\epsilon }^k$ is at most $C\epsilon <\mathrm{\mid }c\mathrm{\mid }\mathrm{/}2$, since each $k_j-k$ is a positive integer; if $C=0$, its sign is constant for every $\epsilon >0$. Thus each such determinant has its formal sign for all sufficiently small positive real $\epsilon$. There are finitely many relevant tuples, so choose one positive real $\epsilon$ small enough for all of them. Use this same value to evaluate the heights of every site. By [F4], each output tetrahedron is a lower simplex of the formal lift. On its affinely independent projected base, every other site's formal support determinant is nonzero by [F2]; the preceding sign specialization preserves its sign. If $O$ is the projected orientation determinant of the base, $h_q$ is the query height, and $\mathrm{\ell }(q)$ is the height of the base graph plane at the query, row subtraction gives the displayed-order identity $P=-O(h_q-\mathrm{\ell }(q))$. As $O\mathrm{\ne }0$ and is unchanged by height specialization, the same four real lifted points support a real lower facet and every other lifted point lies strictly above it. No fifth point is in that facet. Distinct output tetrahedra therefore correspond to distinct facets of this one real convex hull.

If $n=4$, at most one four-site candidate is output, and $1\le 4(4-3)\mathrm{/}2$. If $n\ge 5$, choose four affinely independent projected sites and a fifth distinct site. Their formal determinant is nonzero by [F2], and its real specialization at the common value from step 1.1 is nonzero. Hence the real lifted convex hull is full-dimensional in ${\mathbb{R}}^4$. Let $m\le n$ be its number of extreme vertices; full dimension forces $m\ge 5$.

Apply [F3] to this full-dimensional convex 4-polytope. Its total number of facets, hence also its number of lower facets, is at most $m(m-3)\mathrm{/}2$. By step 1.1, the output tetrahedra inject into those facets. The function $s(s-3)\mathrm{/}2$ is increasing for integers $s\ge 5$, so the output count is at most $n(n-3)\mathrm{/}2$. This is quadratic; the argument establishes no angle or tetrahedral-quality bound.