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

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

• (There is a typo in the title.) Did you try considering even and odd numbers of points separately? Feb 5 '16 at 7:45
• I was thinking of segments of non-intersecting lines. Revisiting this question, I see something not specified: with four points, are the lines going through every other point/crossing each other considered intersecting? They don't share an end point. Anyway, with every line needing two points and no two lines to share points, this looks trivial - ? Feb 5 '16 at 13:37

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