I'm reading CLRS Section 33.4 Finding the closest pair of points. At exercise 33.4-2 they say33.4-2Show 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 belowWhich possibility I'm missing. Can anybody point it out.
Understanding Closest Pair Algorithm (CLRS)
algorithms;computational geometry;divide and conquer
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'.