Efficiently pick a largest set of non-intersecting line segments

Given a set of line segments, how do we identify a subset of maximal cardinality where all line segments are pairwise non-intersecting?

Brute force we would get $2^n$ sets to check where $n$ is the number of line segments, so that isn't viable. Anyone got a bright idea how the do this efficiently? I tried doing it this way: remove a line segment that intersects with the most other line segments, iterate until no line segments intersect anymore; but that didn't work.

Here is a "ready to help me" place, where you can test your solution; it visualizes the set of line segments.

function showAnalysis() {
debug("Just do it");
}


and then click on the top canvas. The fiddle generates randoms segments in the top canvas, and the bottom canvas is the place where an optimal subset will be displayed.

migrated from stackoverflow.comFeb 3 '14 at 20:43

This question came from our site for professional and enthusiast programmers.

• This should be equivalent to the (NP-hard) maximum independent set problem: create a node for each segment, connect nodes if the corresponding segments intersect. Also: "solve this for me" questions are not likely to see any action, this forum expects people to show what they did and ask for help with specific problems. Also: while your website is a good way to test potential solutions, it would be better to have the comments in English since that is the language of this forum. – G. Bach Jan 22 '14 at 14:06
• Thank G. Back. I have tried to remove the line that cross the most of other line, but this is not providing the effect I looking for. There I have really no glue how to start ! But definitively when I get I will do. – Anthony Jan 22 '14 at 14:10
• See Wikipedia on finding maximum independent sets and also two references therein: the wiki article on maximum disjoint sets as well as the paper approximation algorithms for maximum independent set of pseudo-disks. – MvG Jan 22 '14 at 15:50
• I can see how this problem would reduce to the maximum independent set problem, but I'm not seeing the reduction the other direction. Are you sure the two problems are equivalent? It's possible this problem could have a polynomial time solution (although I'd bet not). – Teepeemm Jan 22 '14 at 16:39
• Any planar graph is the intersection graph of some line segments in the plane (Scheinerman's conjecture), and Independent Set is NP-hard on planar graphs, so the problem is NP-hard. – Falk Hüffner Jan 24 '14 at 16:03

You can speed it up somewhat. Let n be the number of segments you have, then you can do a binary search like this: start out with checking whether there is a set with k1 := n/2 segments. If there is, check k2 := n*3/4, if there isn't, check k2 := n*1/4. Always remember all sets of the largest size for which you know that there exists something, because going up only supersets of those can work.