3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ (There is a typo in the title.) Did you try considering even and odd numbers of points separately? $\endgroup$
    – greybeard
    Feb 5, 2016 at 7:45
  • $\begingroup$ 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 - ? $\endgroup$
    – greybeard
    Feb 5, 2016 at 13:37

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.