Arya, Sunil ;
da Fonseca, Guilherme D. ;
Mount, David M.
On the Combinatorial Complexity of Approximating Polytopes
Abstract
Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter $diam(K)$ is given in Euclidean ddimensional space, where $d$ is a constant. Given an error parameter eps > 0, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most eps diam(K). By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A wellknown result by Dudley implies that O(1/eps^{(d1)/2}) facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is Otilde(1/eps^{(d1)/2}), where Otilde conceals a polylogarithmic factor in 1/eps. This is an improvement upon the best known bound, which is roughly O(1/eps^{d2}).
Our result is based on a novel combination of both new and old ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a widthbased variant of Barany and Larman's economical cap covering, which may be of independent interest. Finally, we use a deterministic variation of the witnesscollector technique (developed recently by Devillers et al.) in the context of our stratified construction.
BibTeX  Entry
@InProceedings{arya_et_al:LIPIcs:2016:5903,
author = {Sunil Arya and Guilherme D. da Fonseca and David M. Mount},
title = {{On the Combinatorial Complexity of Approximating Polytopes}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {11:111:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5903},
URN = {urn:nbn:de:0030drops59034},
doi = {10.4230/LIPIcs.SoCG.2016.11},
annote = {Keywords: Polytope approximation, Convex polytopes, Macbeath regions}
}
2016
Keywords: 

Polytope approximation, Convex polytopes, Macbeath regions 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

2016 