Finding the Closest Pair of Points Problem: Given n ordered pairs x1, y

Download 59 Kb.
Size59 Kb.
1   2   3   4   5   6   7   8   9   10
Can we do better?
Here's the idea:
1) Split the set of n points into two halves by a vertical line. (We can do this by sorting all the points by their x-coordinate and then picking the middle point and drawing a vertical line just to the left or right of it.)

2) Recursively call the function to solve the problem on both sets of points.

3) Return the smaller of the two values.

What's the problem with this idea?

The problem is that the actual shortest distance between any two of the original points MIGHT BE between a point from the first set and a point in the second set! Consider this situation:

Share with your friends:
1   2   3   4   5   6   7   8   9   10

The database is protected by copyright © 2020
send message

    Main page