2
$\begingroup$

I've been studying the closest pair algorithm lately and I found this to be an extremely good and intuitive resource: http://serverbob.3x.ro/IA/DDU0221.html. It is also explained in section 33.4, "Finding the closest pair of points" of introduction to algorithms, third edition by CLRS.

I understand why I'd need 7 comparisons for a non pairwise distinct set of points and only 5 otherwise (33.4-2). Both of them follow from the fact that I can fit only 4 points, at least Delta away from each other, on a Delta x Delta box.

What I've been wondering though, is if I could trim the number of comparisons down to 3 if I included only points strictly less than Delta away from the middle line, in the middle Delta x 2 Delta strip. The reasoning is that I already have a pair of points Delta away from each other from the recursive calls, I only need points less than Delta and I can only fit 2 points Delta away from each other AND less than Delta from the middle line on each side.

Have I missed something or can I really just compare the 3 following points of every point in a middle strip only containing points strictly less than Delta from the center?

Edit: I have started a bounty for a very similar question on stack overflow also and we have come up with a very interesting discussion there. So I'm linking it here. We've also started a very insightful chat here.

$\endgroup$
2
+50
$\begingroup$

Yes, as you have observed, we can just compute pair of points whose distances are strictly less than $\delta$ in the "combine" step of the "divide-conquer-combine" algorithm, where we examine the minimal distance between the points to the left and the points to the right.

However, it is not enough to just compute the next 3 points.


Picture from section 33.4 of CLRS, third edition

The above graph, taken from CLRS, illustrates the original argument for 7 in the case of non-pairwise distinct points and for 5 in the case of pairwise distinct points. For the sake of clearer explanation, assume the central line $l$ is the vertical axis and $\delta=\delta_L=\delta_R=1000$. Let the strip consist of the area between the line $x=1000$ and $x=1000$, excluding those two lines. This strip contains only the points that are strictly less than 1000 away from the central line $l$. Suppose all distinct points in the strip in the ascending order of vertical coordinate are $s_0, s_1, s_2, s_3, s_4$.

Suppose we have verified that $d(s_0,s_i)\ge1000$ for $i=1,2,3$. Can we conclude that there is no point $s$ such that $d(s_0,s)<1000$?

No. It might happen that
$$\begin{align}\\ s_0&=(79,0)\\ s_1&=(-921,1)\\ s_2&=(999,500)\\ s_3&=(-999, 998)\\ s_4&=(79, 999) \end{align}$$

Note that $d(s_0, s_4)= 999<1000$. In fact, $d(s_i,s_j)\gt1000$ for all $i$ and $j$ except $d(s_0, s_4)$.
$$\begin{align} d(s_0, s_1)&=\sqrt{1000001} \\ d(s_0, s_2)&=\sqrt{1096400} \\ d(s_0, s_3)&=\sqrt{2158088} \\ d(s_0, s_4)&=\sqrt{998001} \\ d(s_1, s_2)&=\sqrt{3935401} \\ d(s_1, s_3)&=\sqrt{1000093} \\ d(s_1, s_4)&=\sqrt{1996004} \\ d(s_2, s_3)&=\sqrt{4240008} \\ d(s_2, s_4)&=\sqrt{1095401} \\ d(s_3, s_4)&=\sqrt{1162085} \\ \end{align}$$ So if we only compute the distance with the next 3 points, we will not find that shortest edge from $s_0$ to $s_4$ at the end of the algorithm.

The above counterexample shows that it is not sufficient to just compare 3 following points of every point in a middle strip only containing points strictly less than $\delta$ from the center line, even if we assume that all points are distinct.

$\endgroup$
  • $\begingroup$ Right after looking at the coordinates you provided, I noticed how wrong I was in my assumption that I can fit at most 2 points, δ away from each other and less than δ away from l. I thought that was the case because if I were to fit 3 points in the corners of a square of side δ and then started moving the 2 points on one edge closer to the 3rd point, then that 3rd point would be force out of the square to keep the minimum distance of δ. But that is not the case. The 3rd point could move towards the center of the edge, ultimately forming an equilateral triangle. $\endgroup$ – Danilo Souza Morães Jan 12 at 10:51
  • $\begingroup$ Do you think it would be fair to say that when implementing this algorithm, it would be slightly more efficient (not asymptotically though) to build the middle strip with points less than δ away from l just to avoid comparing points that we already know are at least δ away from each other? Most implementations of this algorithm on the internet build the middle strip with points less than or equal to δ from l. $\endgroup$ – Danilo Souza Morães Jan 12 at 11:04
  • $\begingroup$ Yes, your observation does improve the performance of the algorithm. In fact, the bigger improvement might comes from the fact that 4 is enough as said in the other question of your (I may write a proof for that fact). Once the dust is settle down, I suggest that you update Wikipedia entry to mention these two observations. $\endgroup$ – Apass.Jack Jan 12 at 13:52
  • $\begingroup$ It is unfortunate that you have passed the bounty to the question on stackoverflow too early to a fundamentally flawed answer, although you can still switch to accept another answer. $\endgroup$ – Apass.Jack Jan 12 at 14:55
  • $\begingroup$ According to CLRS, we can fit at most 8 points in a 2𝛿 x 𝛿 rectangle and so we need 7 comparisons. What the other answer and yours helped me understand is that I can fit at most 3 points in a 𝛿 x $\dfrac{\sqrt(3)𝛿}{2}$ rectangle, hence 6 points in a 2𝛿 x 𝛿 rectangle, rendering a total of 5 comparisons if we can ensure the middle strip is constructed with points on the x axis strictly less than 𝛿. I can safely get to this conclusion by simply using the same proof CLRS provided. I just need to prove the maximum possible number of points in the middle strip. $\endgroup$ – Danilo Souza Morães Jan 12 at 20:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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