CODEWITHSUNDEEP
algorithmmathoptimizationdata-structuresgeometry
Ωmega
Ωmega

Reputation: 43663

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

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.

Upvotes: 3

Views: 2143

Answers (2)

user1443778
user1443778

Reputation: 591

Use a k-dim tree index (in this case k=2) so a quad tree. This should allow you to efficiently search the space to the left,right,up and down of your point. You can probably formulate a query in a dmbs for this but conceptually I would search the points own "quad" and then depending on the position of the point in the quad we can know if we found the nearest point in one direction or not. Then we know which quads to search for the rest of the points.

Since you are doing this for each point you know there exists symmetry i.e. point P1 has P2 as nearest left neighbor so P2 has P1 as nearest right neighbor. So update the point objects accordingly.

Upvotes: 1

Cybercartel
Cybercartel

Reputation: 12592

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

enter image description here

Upvotes: 1

Related Questions