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})

Back to Abstracts Last modified: Fri Nov 19 22:34:30 EST 1999