You will apply the Closest pair algorithm to the following collection of points (sorted by x-coordinate):...

 

Transcribed Image Text:

You will apply the Closest pair algorithm to the following collection of points (sorted by x-coordinate): (1,3), (1, 7), (2, 4), (2, 9), (3, 1), (3, 5), (4, 3), (4, 7), as outlined in the steps below. You can use that the smallest distance between any pair of points in the left half is 8 = 2 1.41 (between (1,3) and (2, 4)) and the smallest distance between any pair of points in the right half is 82 = 5 2.24 (between ((3, 1) and (4,3)). 1. What points are in L, the left half, and what points are in R, the right half? 2. Identify the largest x-coordinate in the left-half. (We will call this median element X) 3. List all points with x-coordinate between X-8 and X + 8, where 8 denotes the smaller of 8 and 82, defined above. List these points sorted by increasing y-coordinate. (For reference, here is the original list of points, sorted by y-coordinates: (3, 1), (1,3), (4, 3), (2, 4), (3, 5), (1, 7), (4, 7), (2, 9).) 4. Based on your answer to part 2, what are the split pairs (that is, one point in the pair is from the left half and the other point in the pair is from the right half) that we have to examine to determine the overall smallest distance? Determine the distance between these pairs to find a closest overall pair and distance. You will apply the Closest pair algorithm to the following collection of points (sorted by x-coordinate): (1,3), (1, 7), (2, 4), (2, 9), (3, 1), (3, 5), (4, 3), (4, 7), as outlined in the steps below. You can use that the smallest distance between any pair of points in the left half is 8 = 2 1.41 (between (1,3) and (2, 4)) and the smallest distance between any pair of points in the right half is 82 = 5 2.24 (between ((3, 1) and (4,3)). 1. What points are in L, the left half, and what points are in R, the right half? 2. Identify the largest x-coordinate in the left-half. (We will call this median element X) 3. List all points with x-coordinate between X-8 and X + 8, where 8 denotes the smaller of 8 and 82, defined above. List these points sorted by increasing y-coordinate. (For reference, here is the original list of points, sorted by y-coordinates: (3, 1), (1,3), (4, 3), (2, 4), (3, 5), (1, 7), (4, 7), (2, 9).) 4. Based on your answer to part 2, what are the split pairs (that is, one point in the pair is from the left half and the other point in the pair is from the right half) that we have to examine to determine the overall smallest distance? Determine the distance between these pairs to find a closest overall pair and distance.