inria-00412352, version 1
Lower and upper bounds on the number of empty cylinders and ellipsoids
Oswin Aichholzer 1Franz Aurenhammer 2Olivier Devillers
a, 3Thomas Hackl 1Monique Teillaud
a, 3Birgit Vogtenhuber 1
European Workshop on Computational Geometry (2009) 139-142
Résumé : 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 several ways. Among various results we prove that the number of empty circular cylinders is between Omega(n3) and O(n4) while we have a tight bound Theta(n4) for empty ellipsoids. We also take interest in pairs of empty homothetic ellipsoids, with application to the number of combinatorially distinct Delaunay triangulations obtained by orthogonal projections of S on a two-dimensional plane, which is Omega(n4) and O(n5). A side result is that the convex hull in d dimensions of a set of n points, where one half lies in a subspace of odd dimension delta > 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^(d/2-1)).
- a – INRIA
- 1 : Institute for Software Technology [Graz] (IST)
- Graz University of Technology – Technische Universität Graz
- 2 : Institute for Theoretical Computer Science
- Graz University of Technology
- 3 : GEOMETRICA (INRIA Sophia Antipolis / INRIA Saclay - Ile de France)
- INRIA
- Domaine : Informatique/Géométrie algorithmique
- inria-00412352, version 1
- http://hal.inria.fr/inria-00412352
- oai:hal.inria.fr:inria-00412352
- Contributeur : Olivier Devillers
- Soumis le : Mardi 1 Septembre 2009, 15:03:19
- Dernière modification le : Vendredi 13 Novembre 2009, 09:30:08






Documents associés
Exporter