0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ I think you may be confused. $n^2$ is brute force... $\endgroup$
    – Lev Reyzin
    Nov 17, 2011 at 22:12
  • $\begingroup$ Yes I know that. But if all points share the same x-coordinate, all the points land in the same set in the deivide step, don't they? $\endgroup$ Nov 17, 2011 at 22:35

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ I feel like an explanation of how the algorithm degenerates, and how to avoid it, is missing for this to be an answer. $\endgroup$
    – Bladt
    Jun 22 at 17:35
  • 1
    $\begingroup$ This is a technical issue that can be dealt with more easily than with symbolic perturbation in this case. On the other hand this is not a research level question. I can imagine this being an exercise in an algorithms class after teaching the closest pair divide and conquer algorithm. $\endgroup$ Jun 23 at 1:49
1
$\begingroup$

The input then is boring, and the algorithm is bored it takes it much longer to solve the problem.

$\endgroup$
2
  • 3
    $\begingroup$ There is no such thing as a boring input. $\endgroup$ Nov 18, 2011 at 0:19
  • 3
    $\begingroup$ Theorem: There is no such thing as an interesting natural number. Proof: Let n be the smallest interesting natural number. Who cares? QED. $\endgroup$
    – Jeffε
    Nov 22, 2011 at 9:51
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.