# Partitioning a set based on a non-equivalence relation

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.

This problem is called Interval Partitioning Problem, and it can be solved in $$O(n\log n)$$ time by a greedy algorithm.
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.
• 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. Commented Feb 25, 2023 at 4:15