6

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

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
TimeToCodeTheRoad
  • 7,032
  • 16
  • 57
  • 70
  • 2
    What is your question? Are you looking for a solution that is faster than `O(N*N)`? – Sergey Kalinichenko Jan 16 '12 at 17:55
  • 4
    This is an quite bad interview question, especially if the goal is to come up with actual code. It is trivial to get a working solution (whose complexity may be acceptable in some contexts), as you roughly did, but quite hard to improve upon it. Especially if you have no clue about the structures used in computational geometry. Anyway, googling for "nearest neighbo(u)r" should give you a lot of pointers. A good start is [this Wikipedia entry](http://en.wikipedia.org/wiki/Nearest_neighbor_search) – Alexandre C. Jan 16 '12 at 17:56
  • @dasblinkenlight, no he looks for algorithm to run in O(n^n). – Saeed Amiri Jan 16 '12 at 17:57
  • Actually, there seems to be a `O(n log n)` solution [in that paper](http://www.springerlink.com/content/p4mk2608787r7281/?p=09da9252d36e4a1b8396833710ef08cc&pi=8). – Alexandre C. Jan 16 '12 at 18:01
  • possible duplicate of [All k nearest neighbors in 2D, C++](http://stackoverflow.com/questions/4172358/all-k-nearest-neighbors-in-2d-c) – Alexandre C. Jan 16 '12 at 18:03
  • 1
    Your interviewer like points? your previous question was about this, is this homework or your exam problems? – Saeed Amiri Jan 16 '12 at 18:04
  • @dasblinkenlight: i am looking for a solution faster than O(n*n) – TimeToCodeTheRoad Jan 16 '12 at 18:27

2 Answers2

4

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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
3

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."

Joseph O'Rourke
  • 4,346
  • 16
  • 25