(a) Suppose you are given two sets of n points, one set P1,P2, .Pn on the line y0 and the other set {gi,92, .. .In^ on the line y1. Create a set of n line segments by connecting each point pi to the corresponding point g. Your goal is to develop an algorithm to determine how many pairs of these line segments intersect. Your algorithm should take the 2n points as input, and return the number of intersections. It should run in O(n logn) time. An example for the line intersection problem Describe a divide and conquer algorithm for this problem. Prove its correctness and analyze its running Hint: What does this problem have in common with the problem of counting inversions in a list? Can you "reduce" (or "translate") this problem to the problem of counting inversions in an appropriately defined list? (b) Now suppose you are given two sets P = {P1,P2, . . . , Pn} and Q ,92,-. . ,Yn} of n points on the unit circle. Connect each point p, to the corresponding point q. Once again our goal is to determine the number of intersections amon Note that the number of intersections do not depend on the actual positions of the points along the circle but only on their position relative to other points, for example, for each i, which other pairs (Pj-lj) have exactly one end-point in the arc clockwise from p, to qi. Therefore, for simplicity we will assume that the points are numbered and specified according to their appearance in clockwise order starting from some arbitrary location, call it "origin", on the circle. So, for example, if P1 : 3, then P1 is the third point clockwise from the origin in the set PUQ(as in the figure below, where origin is denoted with a green asterisk). ng the resulting line segments P. Given the sets P and Q in this format, we will develop a divide and conquer algorithm to determine the number of intersections. Imagine splitting the circle into two parts, each of which contains half the points What subproblems do these parts correspond to? Determine how to solve each of these subproblems, and put the components together in order to achieve an overall solution. Prove the O(n log2n) time. Hint: Use your solution to part (a) as a subroutine. correctness of your algorithm and analyze its running time. Your algorithm should run in (a) Suppose you are given two sets of n points, one set P1,P2, .Pn on the line y0 and the other set {gi,92, .. .In^ on the line y1. Create a set of n line segments by connecting each point pi to the corresponding point g. Your goal is to develop an algorithm to determine how many pairs of these line segments intersect. Your algorithm should take the 2n points as input, and return the number of intersections. It should run in O(n logn) time. An example for the line intersection problem Describe a divide and conquer algorithm for this problem. Prove its correctness and analyze its running Hint: What does this problem have in common with the problem of counting inversions in a list? Can you "reduce" (or "translate") this problem to the problem of counting inversions in an appropriately defined list? (b) Now suppose you are given two sets P = {P1,P2, . . . , Pn} and Q ,92,-. . ,Yn} of n points on the unit circle. Connect each point p, to the corresponding point q. Once again our goal is to determine the number of intersections amon Note that the number of intersections do not depend on the actual positions of the points along the circle but only on their position relative to other points, for example, for each i, which other pairs (Pj-lj) have exactly one end-point in the arc clockwise from p, to qi. Therefore, for simplicity we will assume that the points are numbered and specified according to their appearance in clockwise order starting from some arbitrary location, call it "origin", on the circle. So, for example, if P1 : 3, then P1 is the third point clockwise from the origin in the set PUQ(as in the figure below, where origin is denoted with a green asterisk). ng the resulting line segments P. Given the sets P and Q in this format, we will develop a divide and conquer algorithm to determine the number of intersections. Imagine splitting the circle into two parts, each of which contains half the points What subproblems do these parts correspond to? Determine how to solve each of these subproblems, and put the components together in order to achieve an overall solution. Prove the O(n log2n) time. Hint: Use your solution to part (a) as a subroutine. correctness of your algorithm and analyze its running time. Your algorithm should run in
