# Optimal Approximate Polytope Membership

arXiv: https://arxiv.org/abs/1612.01696 · HTML: https://mlsanity.com/paper/1612.01696/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2016.

## Built on by (most cited first, 3 of 3)

- [Improved Search of Relevant Points for Nearest-Neighbor Classification](https://mlsanity.com/paper/2203.03567/) (2022)
- [Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.13068/) (2021)
- [Uniform Brackets, Containers, and Combinatorial Macbeath Regions](https://mlsanity.com/paper/2111.10048/) (2021)

## Abstract (arXiv)

In the polytope membership problem, a convex polytope K in Rd is given, and the objective is to preprocess K into a data structure so that, given a query point q ∈ Rd, 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 varepsilon > 0, the query can be answered either way if the distance from q to K's boundary is at most varepsilon 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/varepsilond-1) storage, whereas storage O(1/varepsilon(d-1)/2) admits roughly O(1/varepsilon(d-1)/8) query time. In this paper, we present a data structure that achieves logarithmic query time with storage of only O(1/varepsilon(d-1)/2), which matches the worst-case lower bound on the complexity of any varepsilon-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 varepsilon-approximate nearest neighbor queries for a set of n points in O(log fracnvarepsilon) time is reduced to O(n/varepsilond/2). This halves the exponent in the varepsilon-dependency of the existing space bound of roughly O(n/varepsilond), which has stood for 15 years (Har-Peled, 2001).