============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Approximate Polytope Membership Queries
            
Palestrante: Guilherme Dias da Fonseca
             Universidade Federal do Estado do Rio de Janeiro

Hora e Data: 16h00, quinta-feira, 04 de outubro de 2012

Local:       Sala Multi-usos do Numec

Resumo:

We  consider   an  approximate  version   of  a  fundamental
geometric search problem, polytope membership queries. Given
a convex polytope *P* in *d*-dimensional space, 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 allowed error eps.  Previous solutions to
this problem  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  the first significant  improvements 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)). Our  approach is based on  a very simple
construction  algorithm,   whose  analysis  is  surprisingly
nontrivial.  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. Remarkably,  we show  that our
tradeoff provides significant improvements to the best known
space-time   tradeoffs  for  approximate   nearest  neighbor
searching. Furthermore, this  is achieved with constructions
that are much simpler than existing methods.

Join work with Sunil Arya and David Mount from STOC 2011.