Please help me with Question 3 only. I got question 2 over this link: http://www
ID: 3565481 • Letter: P
Question
Please help me with Question 3 only. I got question 2 over this link:
http://www.chegg.com/homework-help/questions-and-answers/please-provide-complete-solution-q6008227
Pleae help me with this question with complete solution!!!!
We define the Li distance between two points (x1,y1) and (x2y2) to be |x1-x2|+|y1-y2|. Give a set, P, of points, in which each point is colored either "red" or "blue", our task is to compute the Li-closest red-blue pair, i.e., a pair of points p and q, where p is a red point and q is blue, such that the L1-distance between p and q is minimized. You may assume that all coordinates are distinct. In this question, you are asked to solve the problem of finding the L-closest red-blue pair in n given points in the following special case: In this case, all red points are in region {(x,y)|x > a, y > b} and all blue points are in {(x,y)|xExplanation / Answer
i am giving the solution for question 3rd as i have already provide solution of 2nd . as you know we have a point y = h. we are given a list of points which are either red or blue. if we notice this points are in form (xi,yi) where yi is greater than h for blue points and less than h for red points.
1) make two array sorted by y one contains the blue point other contains the red points.
2) make a function find minimum taking two array one of blue and other of red and find the minimum pair among these arrays by divide it further.
3) now look at the arrays we make out of n given points. these array are like
[b1, b2 , b3 .... bi] [r1, r2 , r3 .... rj] are two array containing blue and red points in increasing y - coordinates. now take 2nd half of 1st array and 1st half of 2nd array and pass it in the function defined in point 2 and calculate the minimum distance d1. similarly pass the 1st half of 1st array and 2nd half of 2nd array to above function calculate the minimum distance d2. return the answer min (d1,d2).
time complexity :- each time array is divided into two parts to calculate the minimum distance pair. so O (n log n)
Pseudo Code :
divide the given array of point into two array such that one contains all blue points and other contains all red points.
pass the 1st half of 2nd array and 2nd half of 1st array and calculate the distance d1. pass 2nd part of 2nd array and 1st half of 1st array and calculate distance d2. return min (d1,d2).
function calculate (array b[],array r[]):
if (length of b == 1 and length of red == 1 ):
return distance between them
else if (length of b == 1 or length of red == 1):
return minimum distance of this point with the other of the other array
else
recursively call the function for (left half of b and right half of r) and (right half of b and left half of r).