Optimal approximate polytope membership
Sunil Arya, Guilherme Dias da Fonseca, David M. Mount · Symposium on Discrete Algorithms · 2017
In the polytope membership problem, a convex polytope K in ℝd is given, and the objective is to preprocess K into a data structure so that, given a query point q ∈ ℝd, it is possible to determine efficiently whether q ∈ K. We consider this problem in an approximate setting and assume that d is a constant. Given an approximation parameter e > 0, the query can be answered either way if the distance from q to K's boundary is at most e times K's diameter. Previous solutions to the problem were on the form of a space-time trade-off, where logarithmic query time demands O(1/ed−1) storage, whereas storage O(1/e(d−1)/2) admits roughly O(1/e(d−1)/8) query time. In this paper, we present a data structure that achieves logarithmic query time with storage of only O(1/e(d−1)/2), which matches the worst-case lower bound on the complexity of any e-approximating polytope. 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 e-approximate nearest neighbor queries for a set of n points in O(log n/e) time is reduced to O(n/ed/2). This halves the exponent in the e-dependency of the existing space bound of roughly O(n/ed), which has stood for 15 years (Har-Peled, 2001).