Let {P1, P2, Pn} and {91, 92, 9n} be two sets of points given on two...

Transcribed Image Text:

Let {P1, P2, Pn} and {91, 92, 9n} be two sets of points given on two parallel lines, the p;s on the line y = 1 and the qis on the line y = 2. Consider the line segments connecting p to q. P2 to 92, and pn to qn. See, for example, Figure 1 for n = 5. P4 P1 P5 P2 P3 92 91 94 93 95 Figure 1 Design a divide-and-conqure algorithm to compute the number of intersections of all the line segments. Your algorithm should run in time at most O(n log n). You can assume that all the points on both lines are distinct. Let {P1, P2, Pn} and {91, 92, 9n} be two sets of points given on two parallel lines, the p;s on the line y = 1 and the qis on the line y = 2. Consider the line segments connecting p to q. P2 to 92, and pn to qn. See, for example, Figure 1 for n = 5. P4 P1 P5 P2 P3 92 91 94 93 95 Figure 1 Design a divide-and-conqure algorithm to compute the number of intersections of all the line segments. Your algorithm should run in time at most O(n log n). You can assume that all the points on both lines are distinct.