CATS-Sept-30-2016
Title[edit]
Low Complexity Convex Approximation
Speaker[edit]
Dave Mount
Abstract[edit]
The problem we will discuss is how to approximate a convex body in d-dimensional space as a polytope having a small combinatorial complexity (that is, having a small number of vertices, edges, and faces). It has been known for decades that in dimension d it is possible to eps-approximate any convex body of unit diameter using O(1/eps^{d/2}) vertices. Here, it is assumed that d is a constant. Unfortunately, the number of facets could be much larger, roughly the square of this. It has been a longstanding open problem whether there exists an approximating polytope such that the number of faces of all dimensions matches the bound on the number of vertices.
In this talk, I will demonstrate a construction where the number of faces of all dimensions is O(1/eps^{d/2}) (up to polylog factors). Along the way, I'll introduce a a few cool geometric concepts, in particular, Macbeath regions and the witness-collector method.
This is joint work with Sunil Arya and Guilherme da Fonseca (two UMD alums), and is based on a paper I presented recently at SoCG 2016.
