Approximation Algorithms and Geometric Convexity

Imre Bárány (Rényi Institute of Mathematics & UCL) |
Vector-sum theorems, their relatives and applicationsAbout hundred years ago, answering a question of Riemann, Steinitz proved the following result. Let |
---|---|

Guilherme Dias da Fonseca (Université Clermont Auvergne) |
Geometric Approximation Using Macbeath RegionsThroughout this abstract, let K be a fat convex body of unit diameter in d-dimensional space for fixed d and ε > 0 be an arbitrarily small parameter that controls the approximation error. We recently showed that a packing of disjoint Macbeath regions of K, all having width ε, consists of at most O(1/ε^{(d-1)/2}) such regions. The main objective of this talk is to present three applications of this result to geometric approximation. We will start with the definition of Macbeath regions, their properties, and the idea of the proof of the number of disjoint Macbeath regions of width ε. We then proceed to the applications.
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. |

Kunal Dutta (Inria Sophia Antipolis) |
The Geometric Subset General Position problemThe problem consists of a geometric system, like a system of lines, hyperplanes or spheres, together with We present a new algebraic framework for solving the Geometric Subset General Position problem and its variants. Our framework provides a unified approach to all the known variants that have been studied in the literature, generalizing them from the planar to the |

10h30-12h | Imre Bárány |
---|---|

12h-13h | Lunch (provided) |

13h-13h45 | Working session and coffee |

13h45-14h30 | Kunal Dutta |

14h30-16h | Guilherme Dias da Fonseca |

Contact: bruno.jartoux+aagc@esiee.fr.

Couprie | Michel | ESIEE / LIGM |

Pluta | Kacper | UPEM |

Jacquin | Pascal | ESIEE |

Meunier | Frédéric | Ecole des Ponts ParisTech |

De Loera | Jesus | University of California |

Dutta | Kunal | INRIA Sophia-Antipolis |

Jartoux | Bruno | LIGM, ESIEE Paris |

Mustafa | Nabil H. | LIGM, ESIEE Paris |

Bárány | Imre | Rényi Institute of Mathematics & UCL |

Romon | Pascal | UPEM |

Barbudo | Elias | ESIEE Paris |

Dias da Fonseca | Guilherme | Université Clermont Auvergne |

Andres | Hervé | Ecole des Ponts ParisTech |

Chu | Chengbin | ESIEE Paris |

De Albuquerque | Arnaldo | UFMG and ESIEE Paris |

Fradelizi | Matthieu | Université Paris-Est Marne-la-Vallée |

Hubard | Alfredo | Université Paris-Est Marne-la-Vallée |