Closest neighbor to any point (other than itself) in a 2D plane
For a given a point P, simple solution:

Calculate P's distance from all other points, this is done with O(n) time complexity.
Save them as list of tuples (or similar data structure), the tuples of (point, distance from P).
One walk over the list can yield you the top K closest points, in O(n) time complexity.

A second solution that will cost more in space complexity (O(n^2)) and maintenance over time, but will  shorten finding the K nearest neighbors:

Keeping a dictionary from each point to a ordered list (or similar data structure) of points by their distance - building this table once is O(n^2 * log(n)).
Finding K closest points is O(k) - dictionary access + copying k elements from ordered list.
Overhead in time complexity would be in adding a new point or removing an old one in a manner that will keep this data structure valid - O(n*log(n)) in both.

The solution you choose should be on what you want to optimize
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.