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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I think you may be confused. $n^2$ is brute force... $\endgroup$
    – Lev Reyzin ♦
    Nov 17 '11 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$
    – GugenMinded
    Nov 17 '11 at 22:35
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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ There is no such thing as a boring input. $\endgroup$
    – Tsuyoshi Ito
    Nov 18 '11 at 0:19
  • 2
    $\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 '11 at 9:51

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.