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.