hw6 (1).pdf-Adobe Acrobat Reader DC File Edit View Window Help Home Tools hw6 (1).pdfx Sign In 110% Given two points p = (p.z,p.y) and q (q.x. q.y) in the plane, we say that P is northeast of q if p.z 2 q.x, p.y 2 q.y, and at least one of these two inequalities is strict. For example, (4,3) is northeast of (3,2), (3,3) is northeast of (3,2), and (5,2) is northeast of (3,2). Whereas (1,0) is not northeast of (3,2), (4,1) is not northeast of (3,2), (1,4) is not northeast of (3, 2), and (3,2) is not northeast of (3,2) Given a set P of points in the plane, we say that a point q E P is ertreme if no point in P is to the northeast of q. For example, with P= {(1,0), (3,2), (1,4), (4,1), (5,2)), the only extreme points are (1,4) and (5,2) In this assignment, we consider the problem of computing the set of extreme points in a given set P of points. The straightforward algorithm for this works as follows. We consider each point q in P, and determine if it is extreme by going through every other point r in P, and checking if r is to the northeast of q; if no point is to the northeast of q, we add q to the set of extreme points. In this assignment, your task is to develop an algorithm that is substantially faster than the straighforward algorithm on input point sets that are "nicely distributed" To generate a nicely distributed point set with n points, we sample n points as follows: to generate a point p = (p.z.p.y), we let p.z to be a random integer in the range 0,n], and we let p.y to be an independent random integer in the range 0,n -p.r]. This process gives us a set of n points in the triangle formed by the points (0, n), (0,0), and (n. 0) The algorithm you develop should correctly return the set of extreme points in the in- put point set. It should be noticably faster than the straightforward algorithm on nicely distributed point sets. Furthermore, the ratio of the actual running time of the devel oped algorithm to the actual running time of the straightforward algorithm should tend to decrease as we increase n hw6 (1).pdf-Adobe Acrobat Reader DC File Edit View Window Help Home Tools hw6 (1).pdfx Sign In 110% Given two points p = (p.z,p.y) and q (q.x. q.y) in the plane, we say that P is northeast of q if p.z 2 q.x, p.y 2 q.y, and at least one of these two inequalities is strict. For example, (4,3) is northeast of (3,2), (3,3) is northeast of (3,2), and (5,2) is northeast of (3,2). Whereas (1,0) is not northeast of (3,2), (4,1) is not northeast of (3,2), (1,4) is not northeast of (3, 2), and (3,2) is not northeast of (3,2) Given a set P of points in the plane, we say that a point q E P is ertreme if no point in P is to the northeast of q. For example, with P= {(1,0), (3,2), (1,4), (4,1), (5,2)), the only extreme points are (1,4) and (5,2) In this assignment, we consider the problem of computing the set of extreme points in a given set P of points. The straightforward algorithm for this works as follows. We consider each point q in P, and determine if it is extreme by going through every other point r in P, and checking if r is to the northeast of q; if no point is to the northeast of q, we add q to the set of extreme points. In this assignment, your task is to develop an algorithm that is substantially faster than the straighforward algorithm on input point sets that are "nicely distributed" To generate a nicely distributed point set with n points, we sample n points as follows: to generate a point p = (p.z.p.y), we let p.z to be a random integer in the range 0,n], and we let p.y to be an independent random integer in the range 0,n -p.r]. This process gives us a set of n points in the triangle formed by the points (0, n), (0,0), and (n. 0) The algorithm you develop should correctly return the set of extreme points in the in- put point set. It should be noticably faster than the straightforward algorithm on nicely distributed point sets. Furthermore, the ratio of the actual running time of the devel oped algorithm to the actual running time of the straightforward algorithm should tend to decrease as we increase n