I came across the below question and I am unable to find a way to find the closest pair distance using Divide and Conquer for the same, could someone please help?
L is the closest pair distance among all points with negative x co ordinate and R is the closest pair distance among all points with positive x co ordinate.
Assume there are atleast 2 points with positive and 2 points with negative x coordinate. if L<R and that no point has x co ordinate in the interval (-L/2, R/2), What is the Closest Pair Distance?
So, the closest distance between a point of the left (
x <= -L/2) and a point on the right (x >= R/2) is if the two points are on the boundary (with the sameycoordinates): Distance =L/2 + R/2So,
(L/2 + R/2) > (L/2 + L/2) = LIn other words, the shortest between a point that is on the left and one on the right is always greater than
L, soLis the shortest distance.