Invited speakers

Imre Bárány
(Rényi Institute of Mathematics & UCL)
Vector-sum theorems, their relatives and applications

About hundred years ago, answering a question of Riemann, Steinitz proved the following result. Let B be the unit ball of the Euclidean norm in Rd and assume that V⊆B is finite and the sum of the elements in V is zero. Then there is an ordering of the vectors in V such that all partial sums along this ordering have norm smaller than 2d. I am going to talk about extensions, generalizations of this remarkable theorem and its applications in various fields of mathematics and operations research.

Guilherme Dias da Fonseca
(Université Clermont Auvergne)
Geometric Approximation Using Macbeath Regions

Throughout 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 problem

The problem consists of a geometric system, like a system of lines, hyperplanes or spheres, together with n input points in Rd, and a positive integer k. The objective is to find a subset of at least k input points in general position with respect to the specified system. For example, a set of points is in general position with respect to a system of hyperplanes in Rd if no d+1 points lie on the same hyperplane.

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 d-dimensional case, as well as enabling the treatment of a large class of new problems, such as Subset General Position with respect to Algebraic Curves, d-Polynomial Subset General Position, Subset Delaunay Triangulation, Circle Subset General Position etc. along with their analogues in projective, spherical and hyperbolic geometry.

Schedule (provisional)

10h30-12hImre Bárány
12h-13hLunch (provided)
13h-13h45Working session and coffee
13h45-14h30Kunal Dutta
14h30-16hGuilherme Dias da Fonseca

Organisers

Bruno Jartoux and Nabil H. Mustafa (LIGM, ESIEE Paris). The workshop is supported by ANR grant SAGA.
Contact: bruno.jartoux+aagc@esiee.fr.

Participants

CouprieMichelESIEE / LIGM
PlutaKacperUPEM
JacquinPascalESIEE
MeunierFrédéricEcole des Ponts ParisTech
De LoeraJesusUniversity of California
DuttaKunalINRIA Sophia-Antipolis
JartouxBruno LIGM, ESIEE Paris
MustafaNabil H. LIGM, ESIEE Paris
BárányImreRényi Institute of Mathematics & UCL
RomonPascalUPEM
BarbudoEliasESIEE Paris
Dias da FonsecaGuilhermeUniversité Clermont Auvergne
AndresHervéEcole des Ponts ParisTech
ChuChengbinESIEE Paris
De AlbuquerqueArnaldoUFMG and ESIEE Paris
FradeliziMatthieuUniversité Paris-Est Marne-la-Vallée
HubardAlfredoUniversité Paris-Est Marne-la-Vallée