New lower bounds for convex hull problems in odd dimensions
New lower bounds for convex hull problems in odd dimensions
复制标题
奇数维凸包问题的新下界
DOI：
10.1145/237218.237225
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Jeff Erickson
中科院分区：
文献类型：
--
作者：
Jeff Erickson
我们表明，在最坏的情况下，需要ω（ndd/2e -1 +n logn）侧面查询，以确定rd中n个点的凸壳是否简单或确定凸面船体的数量。在任何奇数中，我们的上限都遵循一个直接的广告论点几年来，d维凸huls可以具有ω（NBD/2C）的面积，以前最佳的下限仅是ω（N logn）。 SEIDEL的下限是在平面中检测任意维度和圆形变性的仿射性变性的。
We show that in the worst case, Ω(ndd/2e−1 +n logn) 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 Ω(ndd/2e−1) degenerate facets. While it has been known for several years that d-dimensional convex hulls can have Ω(nbd/2c) facets, the previously best lower bound for these problems is only Ω(n logn). 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 dd/2esum-hard in the sense of Gajentaan and Overmars.