  In the polytope membership problem, a convex polytope $K$ in $\mathbb{R}^d$
is given, and the objective is to preprocess $K$ into a data structure so that,
given any query point $q \in \mathbb{R}^d$, it is possible to determine
efficiently whether $q \in K$. We consider this problem in an approximate
setting. Given an approximation parameter $\varepsilon$, the query can be
answered either way if the distance from $q$ to $K$'s boundary is at most
$\varepsilon$ times $K$'s diameter. We assume that the dimension $d$ is fixed,
and $K$ is presented as the intersection of $n$ halfspaces. Previous solutions
to approximate polytope membership were based on straightforward applications
of classic polytope approximation techniques by Dudley (1974) and Bentley et
al. (1982). The former is optimal in the worst-case with respect to space, and
the latter is optimal with respect to query time.
  We present four main results. First, we show how to combine the two above
techniques to obtain a simple space-time trade-off. Second, we present an
algorithm that dramatically improves this trade-off. In particular, for any
constant $\alpha \ge 4$, this data structure achieves query time
$O(1/\varepsilon^{(d-1)/\alpha})$ and space roughly $O(1/\varepsilon^{(d-1)(1 -
O(\log \alpha)/\alpha)})$. We do not know whether this space bound is tight,
but our third result shows that there is a convex body such that our algorithm
achieves a space of at least $\Omega(
1/\varepsilon^{(d-1)(1-O(\sqrt{\alpha})/\alpha} )$. Our fourth result shows
that it is possible to reduce approximate Euclidean nearest neighbor searching
to approximate polytope membership queries. Combined with the above results,
this provides significant improvements to the best known space-time trade-offs
for approximate nearest neighbor searching in $\mathbb{R}^d$.
