This is the claim: "If j i 8, then the distance between si and sj is > d."

There is some background information that could be of help:

2. [10 points] In the discussion of the closest points algorithm, for simplicity, my slides assumed that distinct points never had the same x coordinate. One implicit use of this simplifying assumption occurs on slide 23, which contains a claim and its proof. The claim stated there is true in general, but the given proof relies on this additional assumption. Specifically: (a) The statement "No two points lie in the same /2 by /2 square, is true (as shown on slide 23) if all points have distinct x-coordinates, but may be false in the general case where that simplifying assumption is violated. Explain why it is false in general. (b) However, the claim stated on that slide remains true even if multiple points have the same x-coordinate. Prove this. Find closest pair with one point in each side, assuming distance Observation: suffices to consider points within of line L. "Almost" the one-D problem again: Sort points in 26-strip by their y coordinate. Only check pts within 8 in sorted list! 7 o 21 8min(12,21) 12 closest pair of points Def. Let s have the ith smallest y-coordinate among points in the 28-width-strip 39 Claim. Ifj- i 2 8, then the 31 distance between s, and s 30 8/2 29 28 8/2 Pf: No two points lie in the_i 27 same 82-by-8/2 square: 2 26 2 2 25 so S 7 points within + of y(s,) 23 2. [10 points] In the discussion of the closest points algorithm, for simplicity, my slides assumed that distinct points never had the same x coordinate. One implicit use of this simplifying assumption occurs on slide 23, which contains a claim and its proof. The claim stated there is true in general, but the given proof relies on this additional assumption. Specifically: (a) The statement "No two points lie in the same /2 by /2 square, is true (as shown on slide 23) if all points have distinct x-coordinates, but may be false in the general case where that simplifying assumption is violated. Explain why it is false in general. (b) However, the claim stated on that slide remains true even if multiple points have the same x-coordinate. Prove this. Find closest pair with one point in each side, assuming distance Observation: suffices to consider points within of line L. "Almost" the one-D problem again: Sort points in 26-strip by their y coordinate. Only check pts within 8 in sorted list! 7 o 21 8min(12,21) 12 closest pair of points Def. Let s have the ith smallest y-coordinate among points in the 28-width-strip 39 Claim. Ifj- i 2 8, then the 31 distance between s, and s 30 8/2 29 28 8/2 Pf: No two points lie in the_i 27 same 82-by-8/2 square: 2 26 2 2 25 so S 7 points within + of y(s,) 23