You are given a circle whose perimeter contains points p1, p2, ..., pn in clockwise order as well as points q1, q2, ..., qn (no order specified). For each i, a segment is drawn from pi to qi. Find the number of intersections in O(n log^2 n) time.
I considered that, with points pi, pj, qi, qj for some 1 <= i < j <= n:
There is no intersection when exactly one of qi, qj is between pi and pj and the other is not.
If the order is pi, pj, qi, qj or pi, qj, qi, pj then pi-qi and pj-qj intersect.
I solved a simpler problem (with n segments drawn between 2 horizontal lines) by counting inversions and tried to do something similar here, but it doesn't seem like the ordering in the circle problem is transitive. I also can't figure out how one would possibly get a runtime of O(n log^2 n). Could anyone give me some pointers on how to go about solving this?
Each segment i can be defined by a pair of numbers (a_i, b_i), where a_i is the angle one end of the segment makes with the center, b_i is the angle the other end of the segment makes with the center, and a_i < b_i. Sort the segments by increasing a_i. Now, walk through the segments in order. Now, say we are looking at segment (a_x, b_x). Any other segment y can be in four groups:
1) a_x < a_y < b_x < b_y
2) a_y < a_x < b_y < b_x
3) a_x < b_x < a_y < b_y
4) a_y < b_y < a_x < b_x
If y intersects x, it is in group 1 or 2. Observe that if we add up the number of segments in group 1 for each x, we have the answer. Since the segments are ordered by a_i, all the segments y in group 1 satisfy x < y. So, for each x, we want the number of y such that x < y and a_y < b_x and b_x < b_y. You can find this with a segment tree where each node contains a sorted array of the b_i in its segment.
The total complexity will be O(n log n) memory and O(n log^2 n) time.