Finding the largest interval using Dynamic programming

Question

http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf I was doing these questions for practice where I came across one that stumped me.

7.(a) Suppose we are given a set L of n line segments in the plane, where each segment has one endpoint on the line y = 0 and one endpoint on the line y = 1, and all 2n endpoints are distinct. Describe and analyze an algorithm to compute the largest subset of L in which no pair of segments intersects.

(b) Suppose we are given a set L of n line segments in the plane, where the endpoints of each segment lie on the unit circle x 2 + y 2 = 1, and all 2n endpoints are distinct. Describe and analyze an algorithm to compute the largest subset of L in which no pair of segments intersects.

I figured out how to do 7a, (the question is a disguised problem to find the largest subset of increasing numbers), in O(n log n) time. Im almost close to giving up on 7b, as I cant figure out a way to do it.

However, is there a way to convert 7b's premise to something more like 7a's? I feel like that's the right way of approaching the problem, and any help in figuring this out would be much appreciated.

Answer 1

I couldn't come up with an O(n*log(n)) algorithm, but here is an O(n²) one.

The idea is that we build a directed graph with vertices representing segments from the given set and edges representing the "lies to the right of" relation.

Let L be the list of segments: {(a₁, b₁), (a₂, b₂), ..., (a_n, b_n)}, where a_k and b_k are k-th segment's endpoints.

Let L' be the list of segments: {(a₁, b₁), (b₁, a₁), (a₂, b₂), (b₂, a₂), ..., (a_n, b_n), (b_n, a_n)}.

Let the vertices of the graph have indices from 1 to 2*n, each index k representing the segment L'[k], i.e. (a_k/2, b_k/2) if k is odd, and (b_k/2, a_k/2) if k is even.

A segment (a₁, b₁) is said to lie to the right of a segment (a₂, b₂) when the points a₁, a₂, b₂, b₁ are placed in a clockwise order on the unit circle.

Note that 1) If one segment lies to the right of another, they don't intersect; 2) If two segments from L don't intersect, two of the four corresponding segments from L' necessarily lie one to the right of another; 3) Any set of non-intersecting segments from L is defined by a series of segments of L', each lying to the right of the previous one.

Outline of the algorithm:

for every k1 from 1 to 2*n:
    for every k2 from 1 to 2*n:
        if (L'[k1].a, L'[k1].b) lies to the right of (L'[k2].a, L'[k2].b):
            add a directed edge (k1, k2) to the graph 
Find the longest path in the graph: (k1, k2, ..., km). 
The answer to the problem is: (k1/2, k2/2, ..., km/2).