Counting quadrics and Delaunay triangulations and a new convex hull theorem

O. Aichholzer, F. Aurenhammer, O. Devillers, T. Hackl, M. Teillaud, and B. Vogtenhueber

Abstract:

Given a set $S$ of $n$ points in three dimensions, we study the maximum numbers of quadrics spanned by subsets of points in $S$ in various ways. We prove that the set of empty or enclosing ellipsoids has $\Theta(n^4)$ complexity. The same bound applies to empty general cylinders, while for empty circular cylinders a gap remains between the $\Omega(n^3)$ lower bound and the $O(n^4)$ upper bound. We also take interest in pairs of empty homothetic ellipsoids, with complexity $\Theta(n^6)$, while the specialized versions yield $\Theta(n^5)$ for pairs of general homothetic cylinders, and $\Omega(n^4)$ and $O(n^5)$ for pairs of parallel circular cylinders, respectively. This implies that the number of combinatorially distinct Delaunay triangulations obtained by orthogonal projections of $S$ on a two-dimensional plane is $\Omega(n^4)$ and $O(n^5)$. A tight bound $\Theta(n^5)$ holds for shape Delaunay triangulations, where the Euclidean metric is replaced by convex elliptic metrics. Our lower bounds are derived from a generic geometric construction and its variants. The upper bounds result from tailored linearization schemes, in conjunction with a new result on convex polytopes which is of independent interest: In even dimensions $ d
$, the convex hull of a set of $n$ points, where one half lies in a subspace of odd dimension  $\delta > \frac{d}{2}$, and the second half is the (multi-dimensional) projection of the first half on another subspace of dimension $ \delta $, has complexity only $O(n^{\frac{d}{2}-1})$.



Reference: O. Aichholzer, F. Aurenhammer, O. Devillers, T. Hackl, M. Teillaud, and B. Vogtenhueber. Counting quadrics and Delaunay triangulations and a new convex hull theorem. INRIA Report 6748, INRIA, Sofia Antipolis, France, 2008.