inria-00343651, version 1
Counting Quadrics and Delaunay Triangulations and a new Convex Hull Theorem
Oswin Aichholzer 1Olivier Devillers
2Franz Aurenhammer 3Thomas Hackl 1Monique Teillaud
a, 2Birgit Vogtenhuber 1
N° RR-6748 (2008)
Résumé : Given a set $\cal S$ of $n$ points in three dimensions, we study the maximum numbers of quadrics spanned by subsets of points in $\cal 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 $\cal S$ on a two-dimensional plane is $\Omega(n^4)$ and $O(n^5)$. 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~\mbox{$\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 $\bigO{n^{\frac{d}{2}-1}}$.
- a – INRIA
- 1 : Institute for Software Technology [Graz] (IST)
- Graz University of Technology – Technische Universität Graz
- 2 : GEOMETRICA (INRIA Sophia Antipolis)
- INRIA
- 3 : Institute for Theoretical Computer Science
- Graz University of Technology
- Domaine : Informatique/Géométrie algorithmique
- Référence interne : RR-6748
- inria-00343651, version 1
- http://hal.inria.fr/inria-00343651
- oai:hal.inria.fr:inria-00343651
- Contributeur : Olivier Devillers
- Soumis le : Mardi 2 Décembre 2008, 14:10:01
- Dernière modification le : Vendredi 13 Novembre 2009, 09:31:57






Documents associés
Exporter