New lower bounds for convex hull problems in odd dimensions

We show that in the worst case, Omega(n ([d/2]?1) + n log n) sidedness quer ies 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 bo und matches known upper bounds in any odd dimension. Our result follows fro m a straightforward adversary argument. A key step in the proof is the cons truction of a quasi-simplicial n-vertex polytope with Omega(n ([d/2]?1)) de generate facets. While it has been known for several years that d-dimension al convex hulls can have Omega(n ([d/2])) facets, the previously best lower bound for these problems is only Omega(n log n). Using similar techniques, we also obtain simple and correct proofs of Erickson and Seidel's lower bo unds for detecting affine degeneracies in arbitrary dimensions and circular degeneracies in the plane. As a related result, we show that detecting sim plicial convex hulls in R-d is [d/2] sum-hard in the sense of Gajentaan and Overmars.