Constructing higher-dimensional convex hulls at logarithmic cost per face
Constructing higher-dimensional convex hulls at logarithmic cost per face
复制标题
以每面对数成本构造更高维的凸包
DOI：
--
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
R. Seidel
中科院分区：
文献类型：
--
作者：
R. Seidel
我们展示了一种处理高维凸包问题的新方法，例如枚举有限点集凸包的所有面或构造此类凸包的面格。对于固定维度，我们的新算法的最坏情况时间复杂度为 O(m 2 -tFlogm)，其中 m 是输入点集的大小，F 是产生的输出的大小。这种对输出大小的依赖性是可取的，因为 F 的范围可以在 ~(1) 和 O(mld/2|) 之间。我们的时间限制比之前针对大范围 F 值实现的最佳限制有所改进。我们新方法中的主要工具是多面体的直线脱壳的概念。
We exhibit a new approach for dealing with higher dimensional convex hull problems, such as enumerating all facets of the convex hull of a finite point set or constructing the facial lattice of such a convex hull. For fixed dimensions our new algorithms have worst case time complexity O(m 2 -tFlogm), where m is the size of the input point set and F is the size of the output produced. Such a dependence on the output size is desirable since F can range between ~(1) and O(mld/2|). Our time bound is an improvement over the best previously achieved bounds for a large range of values of F. The main tool in our new approach is the notion of a straight line shelling of a polytope.