Séminaire

Joint work with Sunil Arya and David M. Mount to appear in SODA 2017. In the polytope membership problem, a convex polytope K in d-dimensional space is given, and the objective is to preprocess K into a data structure so that, given a query point q, it is possible to determine efficiently whether q is inside K. We consider this problem in an approximate setting and assume that d is a constant. Given an approximation parameter eps > 0, the query can be answered either way if the distance from q to K’s boundary is at most eps times K’s diameter. Previous solutions to the problem were on the form of a space-time trade-off. In this paper, we present a data structure that simultaneously achieves logarithmic query time and minimum storage of O(1/eps^(d-1)/2). Our data structure is based on a new technique, a hierarchy of ellipsoids defined as approximations to Macbeath regions. As an application, we obtain major improvements to approximate Euclidean nearest neighbor searching. Notably, the storage needed to answer eps-approximate nearest neighbor queries for a set of n points in logarithmic time is reduced to O(n/eps^d/2). This halves the exponent in the eps-dependency of the existing space bound of roughly O(n/eps^d), which has stood for 15 years (Har-Peled, 2001).