Search for three points closest to each point in a two-dimensional plane

Question

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

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

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 that 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 process for other points

Answer 1

You might want to explore spatial data structures, such as the kd tree or square tree, which provide excellent expected guarantees for finding nearest neighbors. For example, the kd tree may search for the nearest neighbor in O (n) worst case and the expected time O (sqrt N) after performing preprocessing O (n log n).

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

Hope this helps!

Answer 2

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

Change It is not as simple as I meant, according to the correction in the comments. You can use the Delaunay triangulation to find the three nearest neighbors in O (n log n) time, but this requires a little work, as explained by Dickerson, Drysdale and Mek, " Simple algorithms for listing the distances between points and finding k nearest neighbors .