Computing the nearest neighbor of a point in a
high dimensional Euclidean space is an important geometric query
problem. Such problems have numerous applications.
More general questions include:
What is the color of the nearest neighbor? What color is most
frequent in the collection of k nearest neighbors?
The algorithmic complexity of these problems can be improved by
weakening the condition to seeking an approximate nearest neighbor.
The speaker will discuss her recent joint work on these questions
with S. Arya, D. Mount, N. Netanyahu and A. Wu.