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

Here is an O(n²) algorithm.

We have 2n endpoints on the circle. Pick any point and start labeling the points in increasing order starting from 1 in clockwise direction. So, we have points labeled from 1 to 2n. Thus, any line segment l can be represented as (i,j) where i and j are endpoints of l and 1≤i<j≤2n.

Let L_i,j be a subset of L such that l=(a,b) ∈ L_i,j if i ≤ a < b ≤ j. Also, define D[i,j] for 1 ≤ i ≤ j ≤ 2n as the maximum number of non-intersecting lines in L_i,j. We need to find D[1,2n].

We use dynamic programming here. Initialize D[i,i] as 0 and D[i,i+1] as 1 if (i,i+1) is a line segment, otherwise set it as 0. We can build D using the following:

if (i,j) is a line segment :
     D[i,j] = D[i+1,j-1]+1
else if (i,k) is a line segment and i<k<j :
     D[i,j] = max(D[i,j] , D[i+1,k-1]+D[k+1,j]+1)
else if (k,j) is a line segment and i<k<j :
     D[i,j] = max(D[i,j] , D[i,k-1]+D[k+1,j-1]+1)
else :
     D[i,j] = max(D[i,j] , D[i+1,j-1])

Since D occupies O(n²) space and we compute each cell of D in constant time the time complexity of the algorithm is O(n²).

Reference: http://www.cs.toronto.edu/~robere/csc373h/files/A2-sol.pdf

Look under the heading Line Intersections (Redux)

Answer 2

Create two lists. The first list has the ordering created by sweeping counter-clockwise around the circle starting at (1,0). The first endpoint of a segment you hit is marked. The second list is ordered the same, but go clockwise around the circle. In this manner, you now have two lists where the segment endpoints show an ordering for intersection. For example, if the first point in the first list doesn't have its corresponding endpoint first in the second list, then it will intersect with all of the segments which appear before it in the second list. (You need to be careful here in that both points for a line can be before the end of your segment. A simple check eliminates this.) You can then just run the list. The total complexity of this approach seems to be O(n log n) for each list creation and O(n) for running the list.

Answer 3

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).