In the book Introduction to Algorithms of Cormen 3rd edition page 1041 about of Closest Pair of Point divide and conquer algorithm, Is there an error? It's said: "...Create an array Y', which is the array Y with all point not in the 2$\delta$-wide vertical strip removed...", it should be: "...Create an array Y', which is the array Y with all point in the 2$\delta$-wide vertical strip removed..."?

  • 1
    $\begingroup$ Textbooks tend to have errors. They're not infallible scripture. You might have just found a typo. $\endgroup$ – Yuval Filmus Feb 16 '17 at 8:39
  • $\begingroup$ @YuvalFilmus thanks, I agree, however, I can't believe that an error like this has kept through different printings. Do you think so? Or I didn't understand this part of the algorithm? $\endgroup$ – Diego Feb 16 '17 at 14:02
  • $\begingroup$ It might have been introduced in one of the later editions. Or it's just never been pointed out to the authors. $\endgroup$ – Yuval Filmus Feb 16 '17 at 14:03
  • 2
    $\begingroup$ Why do you think this is an error? The goal of the merging algorithm is only to consider points within the $2\delta$-wide strip, so you want to create a new $Y'$ containing only the points within the strip (so you want to remove all the points not in the $2\delta$-wide strip). $\endgroup$ – sdamashek Feb 22 '17 at 16:45

Just the two lines before, (or last two lines of page 1040 if you want) say the following:

Observe that if a pair of points has distance less than $\delta$, both points of the pair must be within $\delta$ units of line $\lambda$. Thus, as Figure 33.11(a) shows, they both must reside in the 2$\delta$-wide

Meaning that if you want to be able to combine them after divide and conquer phases, you specifically are going to look within the 2-$\delta$ range. And this is why the first step is to remove all the points that exceed that limitation, therefore that they do not satisfy such constraint.

You want to keep only the points within that window-range.


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.