1
$\begingroup$

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.

To try it out, please implement your attempt in the following function on the linked site:

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.

$\endgroup$

migrated from stackoverflow.com Feb 3 '14 at 20:43

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

  • 1
    $\begingroup$ 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. $\endgroup$ – G. Bach Jan 22 '14 at 14:06
  • $\begingroup$ 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. $\endgroup$ – Anthony Jan 22 '14 at 14:10
  • 1
    $\begingroup$ 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. $\endgroup$ – MvG Jan 22 '14 at 15:50
  • 1
    $\begingroup$ 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). $\endgroup$ – Teepeemm Jan 22 '14 at 16:39
  • 2
    $\begingroup$ 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. $\endgroup$ – Falk Hüffner Jan 24 '14 at 16:03
2
$\begingroup$

EDIT: Falk Hüffner gave a reduction in his comment to the question, the problem is in fact NP hard. What follows is pretty useless for that reason. I'll leave it up anyway so the answer doesn't look butchered.


This might be an NP-hard problem (as Teepeemm rightly pointed out, I did the reduction in the wrong direction, and I can't come up with one in the right direction), which would mean no one knows a subexponential algorithm. Brute force approach: check all sets whether some segments in them intersect, pick the largest one. This will cost you exponential time.

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.

But to be completely honest, your best bet is to reduce this to SAT and use a SAT-solver. Anything you whip up yourself will pale in comparison to the finely tuned tools that SAT-solvers are nowadays. I don't know whether there is a SAT-solver you can easily use in Javascript though, you might have to use one on your server and let Javascript deal with the interpretation of results. Another option would be to look into the algrithms mentioned on the sites that @MvG linked to in his comment to your question.

$\endgroup$
  • $\begingroup$ Since you seem to get the question (I don't), can you please edit it into shape? Thanks! $\endgroup$ – Raphael Feb 6 '14 at 20:49
  • $\begingroup$ @Raphael Will do. $\endgroup$ – G. Bach Feb 7 '14 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy