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?
no point has x co ordinate in the interval (-L/2, R/2)
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 same y coordinates): Distance = L/2 + R/2
L < R
So, (L/2 + R/2) > (L/2 + L/2) = L
In other words, the shortest between a point that is on the left and one on the right is always greater than L, so L is the shortest distance.