Finding a maximal set of nonintersecting line segments in a unit circle

Question

Let P be a set of n points that divides the unit circle into equal pieces. Let S be a set of m line segments such that their end points are points in P. The points aren't unique per line, meaning several lines can share points. I need to find the biggest subset of S of non intersecting lines. Lines that share an end point are treated as intersecting.

In the great piece of art above, n = 3 and m = 2, connecting all dots will form an equilateral triangle, and the two lines are intersecting.

What I tried doing is to apply dynamic programming, but I can't formulate a recursive relation. I tried enumerating the point P = {1,2,...,n} and claiming something like "Let C[k] be the largest subset using only point from 1 to k etc..." but couldn't relate it to k - 1, plus I didn't take advantage of the fact the the points divide the circle into equal pieces.

Any clues\help will be vastly appreciated. :)

Answer 1

For intervals we have got a similar problem.

In the case of interval two intervals $(x_i,y_i)$ and $(x_j,y_j)$ are intersecting if $x_i \leq y_i \leq x_j \leq y_j $ or $x_j \leq y_j \leq x_i \leq y_i$ is not true.
The problem for intervals is discussed in Maximum non-overlapping intervals in a interval tree.

In your case however lines are intersecting only if you have $x_i \leq x_j \leq y_i \leq y_j \leq x_i$ in circular order. Here $x_i$ and $y_i$ are the circumference distance from a fixed point say the top point.

As suggested in the solution for intervals you can either apply dynamic programming or the greedy algorithm.