Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
复制标题
近似多面体组合复杂度的最优界
DOI：
10.1145/3559106
复制
发表时间：
2019
影响因子：
1.3
通讯作者：
D. Mount
中科院分区：
文献类型：
--
作者：
Rahul Arya;S. Arya;Guilherme D. da Fonseca;D. Mount
本文考虑如何用多面体简洁地逼近多维凸体的问题。给定欧几里德 d 维空间中单位直径的凸体 K（其中 d 是常数）和误差参数 ε > 0，目标是确定一个低组合复杂度的凸多面体，其与 K 的豪斯多夫距离至多为 ε。组合复杂度是指所有维度的面总数。 Dudley 和 Bronshteyn/Ivanov 的经典构造表明 O(1/ε(d-1)/2) 个面或顶点分别是可能的，但都不能同时实现两个边界。在本文中，我们证明可以构造具有 O(1/ε(d-1)/2) 组合复杂度的多胞体，这在最坏情况下是最优的。我们的结果基于凸体的 ε 宽度帽与其极体之间的新关系。利用这种关系，我们能够获得“本质上不同”的近似上限数量的体积敏感界限。我们通过将其与见证收集器方法的变体和经济帽盖的新颖的可变厚度分层结构相结合来实现我们的主要结果。
This article considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body K of unit diameter in Euclidean d-dimensional space (where d is a constant) and an error parameter ε > 0, the objective is to determine a convex polytope of low combinatorial complexity whose Hausdorff distance from K is at most ε. By combinatorial complexity, we mean the total number of faces of all dimensions. Classical constructions by Dudley and Bronshteyn/Ivanov show that O(1/ε(d-1)/2) facets or vertices are possible, respectively, but neither achieves both bounds simultaneously. In this article, we show that it is possible to construct a polytope with O(1/ε(d-1)/2) combinatorial complexity, which is optimal in the worst case. Our result is based on a new relationship between ε-width caps of a convex body and its polar body. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are “essentially different.” We achieve our main result by combining this with a variant of the witness-collector method and a novel variable-thickness layered construction of the economical cap covering.