  We start with a review of the pervasiveness of the nearest neighbor search
problem and techniques used to solve it along with some experimental results.
In the second chapter, we show reductions between two different classes of geo-
metric proximity problems: the nearest neighbor problems to solve the Euclidean
minimum spanning tree problem and the farthest neighbor problems to solve the
k-centers problem. In the third chapter, we unify spatial partitioning trees
un- der one framework the meta-tree. Finally, we propose a dual tree algorithm
for Bichromatic Closest Pair and measure the complexity of batch nearest
neighbor search.
