Partitioning a set based on a non-equivalence relation

Question

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.

Answer 1

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.