Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
Which possibility I'm missing. Can anybody point it out.
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'.
