s'authentifier
version française rss feed

inria-00343651, version 1

Counting Quadrics and Delaunay Triangulations and a new Convex Hull Theorem

Oswin Aichholzer 1, Olivier Devillers () 2, Franz Aurenhammer 3, Thomas Hackl 1, Monique Teillaud () a2, Birgit 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}}$.

  • Domaine : Informatique/Géométrie algorithmique
  • Référence interne : RR-6748
 
  • inria-00343651, version 1
  • oai:hal.inria.fr:inria-00343651
  • Contributeur : 
  • Soumis le : Mardi 2 Décembre 2008, 14:10:01
  • Dernière modification le : Vendredi 13 Novembre 2009, 09:31:57
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...