Closest neighbor to any point (other than itself) in a 2D plane
A simple solution that can yield better results than O(n) on average is using a k-d tree for storing the points. building the tree has a worst case complexity O(nlogn). after that searching is on average O(logn) and worst case O(n) (usually for points away from all the other data).
Also you might be interested in LSH or locality sensitive hashing while it is an approximation approach meaning you won't always get the right answer, for high dimensional data it provides an important speedup with complexity being closely related to the parameters chosen.
Given a 2D plane and N points (n1=(x1,y1), n2=(x2,y2)..., nN=(xN,yN)), what is a fast (O(n) or better) algorithm that will find the closest neighbor of any point (e.g. n1 closest neighbor is n3, n2 closest neighbor is n4). I was thinking about storing it in a dictionary where the keys are the points, and the values are the neighbors.
There seem to be quite a lot of similar questions on SO, but I couldn't find any code in Python or answers that are not in other languages.