Title: Approximate Polytope Membership Queries

Speaker: Sunil Arya, HKUST

Time/Date: Thursday, April 21, 11-12
Location: Room 3530

Abstract:

In this talk, we consider an approximate version of a fundamental
geometric search problem, polytope membership queries. Given a convex
polytope P in d dimensions, the objective is to preprocess P so that
it is possible to determine efficiently whether any query point lies
inside P subject to an allowed error eps. Previous solutions were
based on straightforward applications of classic polytope
approximation techniques by Dudley (1974) and Bentley et al
(1982). The former yields minimum storage, the latter yields constant
query time, and a space-time tradeoff can be obtained by interpolating
between the two. We present a significant improvement to this
tradeoff. For example, using the same storage as Dudley, we reduce the
query time from O(1/\eps^{(d-1)/2}) to O(1/\eps^{(d-1)/4}). To
establish the relevance of our results, we introduce a reduction from
approximate nearest neighbor searching to approximate polytope
membership queries, providing significant improvements to the best
known space-time tradeoffs for approximate nearest neighbor searching.