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?
Full text and comments »