One-Day Workshop on
Approximation Algorithms and Geometric Convexity

The first application is in discrete geometry. Approximating convex bodies succinctly by polytopes is a fundamental problem in the field. We are given K and ε and the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most ε. 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/ε.
The second application consists of a data structure problem. In the polytope membership problem we are given K and the objective is to preprocess K into a data structure so that, given any query point q, it is possible to determine efficiently whether q is inside K. We consider this problem in an approximate setting. Given an approximation parameter ε, the query can be answered either way if the distance from q to K's boundary is at most ε. We present an optimal data structure that achieves logarithmic query time with storage of only O(1/ε^{(d-1)/2}). Our data structure is based on a hierarchy of Macbeath regions, where each level of the hierarchy is a packing of Macbeath regions of width δ, and the levels are defined for δ decreasing exponentially from 1 to ε. This data structure has major implications to the complexity of approximate nearest neighbor searching.
The third and last application is an algorithmic problem. Given a set S of n points and a parameter ε, an ε-kernel is a subset of S whose directional width is at least (1-ε) times the directional width of S, for all possible directions. Kernels provide an approximation to the convex hull, and therefore are on the basis of several geometric algorithms. We show how the previous hierarchy of Macbeath regions can be used to construct an ε-kernel in near-optimal time of O(n log(1/ε) + 1/ε^{(d-1)/2}). As a consequence, we obtain major improvements to the complexity of other fundamental problems, such as approximate diameter, approximate bichromatic closest pair, and approximate Euclidean minimum bottleneck tree, as well as near-optimal preprocessing times to multiple data structures.