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.