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

* * | * *




Still, however, one could construct a case where ALL the points on each side are within  of the vertical line:
* | *

* | *


* | *

* | *
So, technically speaking, this case is as bad as our original idea where we'd have to compare each pair of points to one another from the different groups.
But, wait, is it really necessary to compare each point on one side with every other point on every other side???
Consider the following rectangle around the dividing line that is constructed by eight /2 x /2 squares. Note that the diagonal of each square is , which is less than . Since each square lies on a single side of the dividing line, at most one point lies in each box, because if two points were within a single box the distance between those two points would be less than , contradicting the definition of . This means, that there are at MOST 7 other points that could possibly be a distance of less than  apart from a given point, that have a greater y coordinate than that point. (We assume that our point is on the bottom row of this grid; we draw the grid that way.)

Now, we come to the issue of how do we know WHICH 7 points to compare a given point with???

The idea is as follows: as you are processing the points recursively, SORT them based on the y-coordinate. Then, for a given point within the strip, you only need to compare with the next seven points!
Here is a pseudocode version of the algorithm. (I have simplified the pseudocode from the book so that it's easier to get an overall understanding of the flow of the algorithm.)

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