CODEWITHSUNDEEP
algorithmcomputational-geometry
TimeToCodeTheRoad
TimeToCodeTheRoad

Reputation: 7312

Finding the three points nearest each point in a 2D plane

You are given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it. These three points ordered by distance.

For example, given a set of points where each line is of the form: ID x-coordinate y-coordinate 

1 0.0 0.0  
2 10.1 -10.1   
3 -12.2 12.2   
4 38.3 38.3   
5 79.99 179.99

Your program should output:

1 2,3,4   
2 1,3,4   
3 1,2,4   
4 1,2,3   
5 4,3,1

This is an interview question I found on an online Forum. I can think of an O(n*n) solution: calculate the distance of each point to every other point. Return the minimum distance points for this point. Repeat the process for the other points

Upvotes: 6

Views: 2583

Answers (2)

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

What they are looking for is if you ever heard of the Delaunay triangulation, which then leads to an O(n log n) algorithm.

Edit. It is not as simple as I implied, as per the correction in the comments. One can use the Delaunay triangulation to find the three nearest neighbors in O(n log n) time, but it requires a bit of work, as explained in the paper by Dickerson, Drysdale and Sack, "Simple Algorithms for Enumerating Interpoint Distances and Finding k Nearest Neighbors."

Upvotes: 3

templatetypedef
templatetypedef

Reputation: 372664

You may want to look into spatial data structures like the k-d tree or quad tree, which give excellent expected-time guarantees for nearest-neighbor searches. For example, the k-d tree can do nearest neighbor searches in O(n) worst-case time and O(sqrt N) expected time after doing O(n log n) preprocessing work.

Alternatively, if you know that the points are mostly randomly distributed, you could consider partitioning space into a collection of buckets of some fixed size. To find the nearest neighbors to a point, you could look at all the points in the same bucket, then all the points in nearby buckets, etc. This should be close to O(n / b) time per point if the points are nicely distributed and there are b buckets.

Hope this helps!

Upvotes: 4

Related Questions