0
$\begingroup$

I have a set of $n$ elements, and a binary relation between these elements. However, this is not guaranteed to be an equivalence relation. (Specifically, the elements are line segments in a plane, and the relation is intersection: if $A$ intersects $B$, and $B$ intersects $C$, $A$ may or may not intersect $C$.)

I would like to partition this set such that no two elements in the same subset intersect. This can be done trivially by putting every element in its own subset. But I would like the number of subsets to be as small as possible (meaning each subset is as large as possible).

Is this a standard problem, and/or is there a standard algorithm to achieve it? My current thought is to use something akin to a greedy algorithm. Start with a single bin, then iterate through the elements. Test each element against each bin; if it intersects with any element in that bin, move on to the next one. If it intersects something in every bin, make a new one. Off the top of my head, this would seem to run in $O(n^2)$ time, since at worst we're comparing every element against every other element. But I'm curious if there's a cleverer algorithm I'm missing—or if there's some pathological input that will make this algorithm use far more subsets than necessary.

$\endgroup$

1 Answer 1

1
$\begingroup$

This problem is called Interval Partitioning Problem, and it can be solved in $O(n\log n)$ time by a greedy algorithm.

You can refer to this courseware for details.

Actually, this problem can be reduced to the Graph Coloring Problem: for each segment $E$ in your problem, there is a corresponding vertex $v_E$ in the constructed graph, and if segment $A$ intersects segment $B$, then there is an edge $(v_A,v_B)$ in the graph.

When segments are in one dimension, the constructed graph is an interval graph, so it can be solved by a greedy algorithm.

$\endgroup$
4
  • $\begingroup$ Thanks! My problem isn't quite the same as this, since the segments are in two dimensions instead of one, so I don't think I can actually get below O(n²). But this algorithm is the one I'm using and I think it's optimal for my case too. $\endgroup$
    – Draconis
    Feb 24, 2023 at 17:39
  • $\begingroup$ Actually, this problem can be reduced to the Graph Coloring Problem: for each segment $E$ in your problem, there is a corresponding vertex $v_E$ in the constructed graph, and if segment $A$ intersects segment $B$, then there is an edge $(v_A, v_B)$ in the graph. When segments are in one dimension, the constructed graph is an interval graph, so it can be solved by a greedy algorithm. When it comes to two dimensions, I am not sure if the constructed graph has some special properties. $\endgroup$ Feb 25, 2023 at 4:15
  • $\begingroup$ That's actually exactly the answer I'm looking for. If you post that one I'll accept it. $\endgroup$
    – Draconis
    Feb 25, 2023 at 4:33
  • $\begingroup$ I have edited my answer. In addition, the greedy algorithm may not get the optimal solution in the two dimensions case. If the constructed graph has no special properties, it may be hard to solve it since the Graph Coloring Problem is NP-hard in general graphs. However, you can try some heuristic/greedy algorithms, which may be efficient enough. $\endgroup$ Feb 25, 2023 at 4:52

Your Answer

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

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