New lower bounds for convex hull problems in odd dimensions

Proceedings of the 12th Annual ACM Symposium on Computational Geometry, 1-9, 1996.

• Download journal version (final except for copy­editing, © 1997 SIAM):
• Official journal version from SIAM (subscription required)

• Download SoCG version (© 1996 ACM):
• Official SoCG version from ACM's Digital Library (subscription or $5 payment required)

• Abstract from the 5th MSI­Stony Brook Workshop on Computational Geometry

Abstract:
We show that in the worst case, Omega(n^{ceiling{d/2}-1} + n log n) sidedness queries are required to determine whether the convex hull of n points in R^d is simplicial, or to determine the number of convex hull facets. This lower bound matches known upper bounds in any odd dimension. Our result follows from a straightforward and completely constructive adversary argument. A key step in the proof is the construction of a quasi­simplicial n­vertex polytope with Omega(n^{ceiling{d/2}-1}) degenerate facets. While it has been known for several years that d­dimensional convex hulls can have Omega(n^floor{d/2}) facets, the previously best lower bound for these problems is only Omega(n log n). Using similar techniques, we also derive simple and correct proofs of Erickson and Seidel's lower bounds for detecting affine degeneracies in arbitrary dimensions and circular degeneracies in the plane. Finally, we show that deciding whether a d­dimensional convex hull is simplicial is ceiling{d/2}SUM­hard, in the sense of Gajentaan and Overmars.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 14 Feb 2002