Please provide complete solution!!!! 2. [10 marks] We define the L1 distance bet

Question

Please provide complete solution!!!!

2. [10 marks] We define the L1 distance between two points (x1, Y1) and (x2, Y2) 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 L1-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 L1-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)x

Explanation / Answer

explanation -> since we are given n points and (a,b); make two integer x and y one keep the smallest distance from point (a,b) for all point which are left to (a,b) i.e blue points and other will keep the shortest distance of red points from point(a,b).
distance between these points will be shortest distance.

Python Code:

def shortest_distance(l,a,b):
   xx,yy = 1000000000
   blue_x,blue_y,red_x,red_y;
   for points in l:
       if (points->x <= a and points-> y <= b):
           res = (a-points->x)+(b-points->y)
           if (res < xx):
               xx = res
               blue_x = points->x
               blue_y = points->y
       else:
           res = (points->x-a)+(points->y-b)
           if (res < yy):
               yy = res
               red_x = points->x
               red_y = points->y
return (red_x - blue_x) + (red_y - blue_y)

time complexity --> O(n)

Pseudo Code:

function (list,a,b)
    xx,yy = INFINITY
    blue_x,blue_y,red_x,red_y
    visit all points given in list:
       if (this point x and y are less than a and b):
           # it means it is blue point
           # cal the point distance from a,b
           res = (a-points->x)+(b-points->y)
           if (new distance (res) < previous distance (xx)):
               # update the blue point co-ordinate which is neraest to a and b
               blue_x = points->x
               blue_y = points->y
               xx = res
       else:
           # do the same thing for red points
           res = (points->x-a)+(b-points->y-b)
           if (new distance (res) < previous distance (xx)):
               # update the blue point co-ordinate which is neraest to a and b
               red_x = points->x
               red_y = points->y
               xx = res
    #after visited all find the shortest distance
    return (red_x - blue_x) + (red_y - blue_y)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.