Simple k-nearest-neighbor algorithm for euclidean data with variable density?

Question

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, though I hope for answers less complex than moving to kd-trees, etc.

Answer 1

Have you looked at this?

http://www.cs.sunysb.edu/~algorith/major_section/1.4.shtml

kd-trees are quite simple to implement, there are standard java/c implementations.

Also:

You may want to post your question here:

https://cstheory.stackexchange.com/?as=1