Proximity problems for point sets residing in spaces with low doubling dimension

Candidate: Adi Gottlieb

Advisor: Richard Cole

In this thesis we consider proximity problems on point sets. Proximity
problems arise in all fields of computer science, with broad application to
computation geometry, machine learning, computational biology, data mining
and the like. In particular, we will consider the problems of approximate
nearest neighbor search, and dynamic maintenance of a spanner for a point
set.

It has been conjectured that all algorithms for these two problems suffer
from the "curse of dimensionality," which means that their run time grow
exponentially with the dimension of the point set. To avoid this
undesirable growth, we consider point sets that occupy a doubling
dimension lambda. We first present a dynamic data structure that uses
linear space and supports a (1+e)-approximate nearest neighbor search of
the point set. We then extend this algorithm to allow the dynamic
maintenance of a low degree (1+e)-spanner for the point set. The query and
update time of these structures are exponential in lambda (as opposed to
exponential in the dimension); when lambda is small, this provides a
significant spead-up over known algorithms, and when lambda is constant
then these run times are optimal up to a constant. Even when no
assumptions are made on lambda, the query and update times of the neighest
neighbor search structure match the best known run times for approximate
nearest neighbor search (up to a constant multiple in lambda). Further,
the stretch of the spanner is optimal, and its update times exceed all
previously known algorithms.