TY - JOUR
T1 - New lower bounds for convex hull problems in odd dimensions
AU - Erickson, Jeff
N1 - Funding Information:
-Part of this research was done while visiting ICSI Berkeley. Supported by MANLAM Fund 120-857 and by the Fund for Promotion of Research at the Technion.
PY - 1999
Y1 - 1999
N2 - We show that in the worst case, Ω(n[d/2]-1 + n log n) sidedness queries are required to determine whether the convex hull of n points in Rd 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 adversary argument. A key step in the proof is the construction of a quasi-simplicial n-vertex polytope with Ω(n[d/2]-1) degenerate facets. While it has been known for several years that d-dimensional convex hulls can have Ω(n[d/2]) facets, the previously best lower bound for these problems is only Ω(n log n). Using similar techniques, we also obtain simple and correct proofs of Erickson and Seidel's lower bounds for detecting affine degeneracies in arbitrary dimensions and circular degeneracies in the plane. As a related result, we show that detecting simplicial convex hulls in Rd is [d/2]SUM-hard in the sense of Gajentaan and Overmars.
AB - We show that in the worst case, Ω(n[d/2]-1 + n log n) sidedness queries are required to determine whether the convex hull of n points in Rd 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 adversary argument. A key step in the proof is the construction of a quasi-simplicial n-vertex polytope with Ω(n[d/2]-1) degenerate facets. While it has been known for several years that d-dimensional convex hulls can have Ω(n[d/2]) facets, the previously best lower bound for these problems is only Ω(n log n). Using similar techniques, we also obtain simple and correct proofs of Erickson and Seidel's lower bounds for detecting affine degeneracies in arbitrary dimensions and circular degeneracies in the plane. As a related result, we show that detecting simplicial convex hulls in Rd is [d/2]SUM-hard in the sense of Gajentaan and Overmars.
UR - http://www.scopus.com/inward/record.url?scp=0032643328&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032643328&partnerID=8YFLogxK
U2 - 10.1137/S0097539797315410
DO - 10.1137/S0097539797315410
M3 - Article
AN - SCOPUS:0032643328
SN - 0097-5397
VL - 28
SP - 1198
EP - 1214
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 4
ER -