@article {15616,
	title = {Approximate polytope membership queries},
	journal = {Proceedings of 43rd Annual ACM Symposium on Theory of Computing},
	year = {2011},
	month = {2011///},
	pages = {579 - 586},
	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
},
	author = {Arya,S. and da Fonseca,G. D and Mount, Dave}
}
