Nearest neighbor and proximity problems in high dimensions

Piotr Indyk
Stanford University

Recently, in the field of Computational Geometry, there has been significant progress in designing algorithms for proximity problems (e.g. nearest neighbor, closest pair, minimum spanning tree) in high-dimensional spaces. The key property of the new algorithms is that the dependence of their running time on the dimension is only polynomial (as opposed to exponential dependence exhibited by previous techniques), while maintaining the sublinear/subquadratic dependence on the number of input points. This comes at a price of approximation: the algorithms find solutions within a factor of c>1 from the optimal ones. In this talk I will review some of those developments, in particular:

• a c-approximation algorithm for nearest neighbor, with query time roughly O(d n^{1/c}) and space O(dn + n^{1+1/c}), where d is the dimension and n is the number of input points
• c-approximation algorithms for the closest pair and minimum spanning tree, with running times roughly O(d n^{1+1/c})