3
$\begingroup$

I'm reading CLRS Section 33.4 Finding the closest pair of points. At exercise 33.4-2 they say

33.4-2

Show that it actually suffices to check only the points in the 5 array positions following each point in the array Y'

But I'm getting 4 array positions following each point in the array Y' will be suffice to check. See the fig below

enter image description here

Which possibility I'm missing. Can anybody point it out.

$\endgroup$
3
$\begingroup$

Assume that a point exists in every corner in the figure (including the inside corners). If points cannot overlap, then you have 6 points that can reside in the 𝛿x2𝛿 box, and since you must be looking at one of them, you need only compare it to the next 5 in Y'.

$\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.