Nearest-neighbor algorithm with directions (left / right / top / bottom)

Question

Having n random points in 2D geometry, for each point p I need to find 4 (or less if not exists) closest points (qa,qb,qc,qd), where qa is the closest left-top point, qb is the closest right-top point, qc is the closest left-bottom point and qd is the closest right-bottom point to point p. Having same x coordinate is considered as left, having same y coordinate is considered as bottom.

What would be the best data structure to store point coordinates and their nearest-neighbor references? What algorithm would be the fastest or the most performed?

Note: This issue is far more then nearest-neighbor algorithm, as for each point 4 neighbor points are needed.

Answer 1

You can try a space filling curve and a quadtree data structure. A space filling curve reduces the 2 dimension to 1 dimension and it works best with power of 2 grids. A quadtree divides the plane into 4 quads. A space filling curve is mathematical function taking 2 variables and gives 1 number as result. It can have also 3,4,5 variables but the most simple is with 2. Because it gives 1 number and takes 2 variables it can help for questions with 2 dimensions or more.

1. http://social.technet.microsoft.com/wiki/contents/articles/9694.tuning-spatial-point-data-queries-in-sql-server-2012.aspx
2. https://www.google.com/search?q=nearest+neigbor+search+space+filling+curve