Linear expected time algorithms for nearest neighbor problems

This thesis presents and analyses a bucketing algorithm that finds a proximity graph in linear expected time when the points are independent identically distributed with a Lipschitz density f, provided f satisfies a weak assumption. From this proximity graph one can either find the minimum spanning tree in $O(n$ log* $n)$ time or solve the all nearest neighbors problem in $O(n)$ time