Incremental Convex Hull Algorithms Are Not Output Sensitive
Incremental Convex Hull Algorithms Are Not Output Sensitive
复制标题
增量凸包算法对输出不敏感
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
David Bremner
中科院分区：
文献类型：
--
作者：
David Bremner
抽象的。多胞形是有限半空间集的有界交集
$ Bbb R$ $^d$。每个多面体也可以表示为凸包 conv
$ cal V $ 其顶点（或极值点）
$ 卡尔 V $ 。凸包问题是从顶点表示转换为半空间表示或（等效于几何对偶性）反之亦然。给定一个排序 v1 。 。 。输入顶点的 vn，经过一些初始化后，增量凸包算法构造半空间描述
$ cal H $ n-k 。 。 。
$cal H$ n 其中
$cal H$ i 是 conv {v1 的半空间描述。 。 。六}。让 mi 表示 |
$ cal H$ i |，令 m 表示 mn 。令 φ(d) 表示
$ d/lceil sqrt{d}
ceil-1 $ ;在本文中，我们给出了多胞体族，其中 mn-1∈Ωmφ(d)) 对于输入的任何排序。我们还给出了一个 0/1 多胞体家族，其中间尺寸具有类似的放大效果。由于 mn-1 不受 m 、 n 和 d 中任何多项式的限制，增量凸包算法在任何合理意义上都不能被视为输出敏感。事实证明，相同的多面体族对于已知的其他主要类型的凸包算法来说也很困难。
Abstract. A polytope is the bounded intersection of a finite set of half-spaces of
$ Bbb R$ $^d$. Every polytope can also be represented as the convex hull conv
$ cal V $ of its vertices (or extreme points)
$ cal V $ . The convex hull problem is to convert from the vertex representation to the half-space representation or (equivalently by geometric duality) vice versa. Given an ordering v1 . . . vn of the input vertices, after some initialization an incremental convex hull algorithm constructs half-space descriptions
$ cal H $ n-k . . .
$cal H$ n where
$cal H$ i is the half-space description of conv {v1 . . . vi} . Let mi denote |
$ cal H$ i |, and let m denote mn . Let φ(d) denote
$ d/lceil sqrt{d}
ceil-1 $ ; in this paper we give families of polytopes for which mn-1∈Ωmφ(d)) for any ordering of the input. We also give a family of 0/1 -polytopes with a similar blowup in intermediate size. Since mn-1 is not bounded by any polynomial in m , n , and d , incremental convex hull algorithms cannot in any reasonable sense be considered output sensitive. It turns out that the same families of polytopes are also hard for the other main types of convex hull algorithms known.