Data: 14/05/2018

Título: On the Combinatorial Complexity of Approximating Polytopes

Palestrante: Guilherme D. da Fonseca, Université Clermont Auvergne
Data: 14 de maio de 2018, 13 h.
Local: Sala 407, Bloco H, Campus Gragoatá, UFF.

Resumo: 

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 d-dimensional space, where d is a constant. Given an error parameter ε > 0, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most ε diam(K). By combinatorial complexity, we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that O(1/ε^(d-1)/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 Õ(1/ε^(d-1)/2), where Õ conceals a polylogarithmic factor in 1/ε. This is a significant improvement upon the best known bound, which is roughly O(1/ε^d-2). Our result is based on a novel combination of both new and old ideas. First, we employ Macbeth 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 width-based variant of Bárány and Larman's economical cap covering, which may be of independent interest. Finally, we use a deterministic variation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.

 Obs: Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; SoCG 2016, 11:1-15, 2016.

 Confira aqui a apresentação