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)).
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00412352
Contributor : Olivier Devillers <>
Submitted on : Tuesday, September 1, 2009 - 3:03:19 PM
Last modification on : Saturday, January 27, 2018 - 1:31:27 AM
Document(s) archivé(s) le : Tuesday, October 16, 2012 - 10:10:21 AM

File

eurocg.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00412352⟩

Share

Metrics

Record views

336

Files downloads

138