Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
The closest pair of points problem deals with the task to find a pair of points with the global minimum distance. There is a problem, when all points share the same x-coordinate, or at least a large number of points.
I just don't know why, I heard the running time becomes $n^2$
What about it? What is the problem, since the proof for the algorithm shows, that at max. 8 points can reside in the $2 \delta \times \delta$ area.
Points with the same x-coordinate do not cause any substantial problem. However, if you implement the divide-and-conquer algorithm carelessly, they may cause a problem. One way to deal with them is by using symbolic perturbation.
The input then is boring, and the algorithm is bored it takes it much longer to solve the problem.
Without the assumption that no points share the same x-coordinate, we run into one of two problems:
One problem occurs if you partition the space by x-coordinate. Say all points have the same x-coordinate. Any partitioning-value will group all points into the same partition. Clearly this means our depth of recursion is not bounded at O(log n) (depending on the exact implementation, this case might never terminate).
If you try to avoid that problem, by partitioning by position in the sorted list instead, you run into problems with the correctness of of the algorithm: You have to deal with the possibility that there can be points in one partition with the same coordinates as a point in the other.
I haven't read the proof for the 7-point the trick, but in Tardos & Kleinberg, they show a proof for a laxer 15 point version of it: Their proof relies on drawing a dividing line for the partition, given by x=pr_x, where pr_x is the x-coordinate for the right most point in the left partition. They expand the line to a vertical band of width 2d, centered on the line. d denotes the distance between the closest points found by the recursive calls. If there's a closer pair that spans our partitions, it must be in this band.
So far so good.
As a step on their way to arrive at the 15 points, they divide the band into an even grid of d/2 by d/2 squares. For the remaining proof, they rely on the claim that no two points can lie in the same square. They prove this by contradiction:
(1) If two points lie in the same square, they must be closer to eachother than d as the squares are d/2 by d/2. (2) If two points lie in the same square, they must be in the same partition.
If two points in the same partition (2) were closer to eachother than d (1), the recursive call would have returned that pair, and d would have been the distance between them, ie. less than d. A contradiction!
Here's the kicker: What guarantees that two points in the same square are on the same partition? Answer: The fact that no two points have the same x-coordinates.
If, as suggested above, we partition by simply taking half the list of points (+/- 1 for lists of uneven length), we could have two points with the same x coordinate, with one going on the left partition, and the other in the right partition. If these points are the closest pair, we are not guaranteed to find them.
In other words, if we don't assume that no two points have the same coordinates, we need to alter our partitioning method, or amend our proof that we can correctly "merge" the solutions found by recursion, in O(n) time.
