Simple k-nearest-neighbor algorithm for euclidean data with highly variable density? An elaboration on this question, but with more constraints.

The idea is the same, to find a simple, fast algorithm for k-nearest-neighbors in 2 euclidean dimensions.  The bucketing grid seems to work nicely if you can find a grid size that will suitably partition your data.  However, what if the data is not uniformly distributed, but has areas with both very high and very low density (for example, the US population), so that no fixed grid size could guarantee both enough neighbors and efficiency?  Can this method still be salvaged?

If not, other suggestions would be helpful.
I'd recommend using a kd-tree or an R-tree. These structures automatically partition the data.

A kd-tree (k-dimensional tree) is a binary tree in which every node is a point. Every non-leaf node splits the space in half along one of the axes. Points on one side of the split form the left subtree, points on another side form the right subtree. A kd-tree has guaranteed space complexity O(n) and average search, insertion and deletion complexity of O(log n). The cost of building the tree is O(n log n) when using an advanced linear median-finding algorithm. The k-nearest-neighbors search boils down to moving down the tree, checking distances to the elements in final subtree and unwinding the recursion up the tree if more elements are needed. kd-trees are easy to implement in memory, but non-trivial to implement on disk. They may need to be rebuilt when changing data.

R-trees (rectangle trees) group nearby objects in minimum bounding rectangles, group the rectangles in larger rectangles, and so on. This means that they can store not only points, but also polygons. The complexity of search is between O(log n) and O(n), depending on the amount of overlap between rectangles. There are various optimization strategies and algorithms for splitting overflowing nodes and bulk-loading. While more complicated, R-trees have advantages over kd-trees. They are more disk-oriented, making them useful for real databases. Unlike non-bulk-loaded kd-trees, they are balanced, and therefore preferred for changing data.

In conclusion, if the data will change after building the tree or you want the data to be stored on disk, I'd use an R-tree, otherwise kd-tree.