| Abstract | We consider an approximate version of a fundamental geo-metric search problem, polytope membership queries. Given
a convex polytope P in Rd, presented as the intersection of
halfspaces, the objective is to preprocess P so that, given a
query point q, it is possible to determine efficiently whether
q lies inside P subject to an error bound ε.
Previous solutions to this problem were based on straight-
forward applications of classic polytope approximation tech-
niques by Dudley (1974) and Bentley et al. (1982). The
former yields minimum storage, and the latter yields con-
stant query time. A space-time tradeoff can be obtained
by interpolating between the two. We present the first sig-
nificant improvements to this tradeoff. For example, using
the same storage as Dudley, we reduce the query time from
O(1/ε
(d−1)/2
) to O(1/ε
(d−1)/4
). Our approach is based on a
very simple algorithm. Both lower bounds and upper bounds
on the performance of the algorithm are presented.
To establish the relevance of our results, we introduce a
reduction from approximate nearest neighbor searching to
approximate polytope membership queries. We show that
our tradeoff provides significant improvements to the best
known space-time tradeoffs for approximate nearest neigh-
bor searching. Furthermore, this is achieved with construc-
tions that are much simpler than existing methods
|
