Lower and upper bounds on the number of empty cylinders and ellipsoids

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 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)).
Type de document :
Communication dans un congrès
European Workshop on Computational Geometry, Mar 2009, Bruxelles, Belgium. pp.139-142, 2009
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00412352
Contributeur : Olivier Devillers <>
Soumis le : mardi 1 septembre 2009 - 15:03:19
Dernière modification le : jeudi 11 janvier 2018 - 16:40:00
Document(s) archivé(s) le : mardi 16 octobre 2012 - 10:10:21

Fichier

eurocg.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00412352, version 1

Collections

Citation

Oswin Aichholzer, Franz Aurenhammer, Olivier Devillers, Thomas Hackl, Monique Teillaud, et al.. Lower and upper bounds on the number of empty cylinders and ellipsoids. European Workshop on Computational Geometry, Mar 2009, Bruxelles, Belgium. pp.139-142, 2009. 〈inria-00412352〉

Partager

Métriques

Consultations de la notice

289

Téléchargements de fichiers

109