# Is there a constant factor approximation algorithm for 2D rectangle coloring problem?

The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the rectangles using minimum number of colors such that any two overlapping rectangles are assigned different colors.

This problem is known to be NP-hard. Xin Han, Kazuo Iwama, Rolf Klein and Andrezej Lingas (Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs) gave an O(log n) approximation. Is there a better approximation algorithm?

We know that the interval coloring problem is solved in polynomial time by first-fit algorithm by considering intervals according to their left endpoints. However, first-fit online algorithm is 8-competitive when the intervals appear in arbitrary order.

What is the performance of the first-fit algorithm for the rectangle coloring problem? What happens to first-fit algorithm when the rectangles appear according to their left (vertical) sides?

Thanks in advance for any help on this.

As suggested by the other answer, $$\Omega(\log n)$$ lower bound is not too hard to see. Let us do the sweeping bottom up with a horizontal line. The idea is to build components that require larger and larger number of colors. In particular, let $$C(i)$$ be a gadget that has a top rectangle with color $$i$$ (i.e., the first fit would assign it color $$i$$). Clearly, $$C(1)$$ is just a single rectangle. The component $$C(2)$$ is
In general, the component $$C(k)$$ is a rectangle with $$C(1), \ldots, C(k-1)$$ hanging below it:
Now, it is easy to verify that a fit-first algorithm with sweeping horizontally from the bottom would use $$k$$ colors to color $$C(k)$$. However, the intersection graph of $$C(k)$$ is just a tree, and it can be colored by $$2$$ colors. Now, $$C(k)$$ is just a Fibonacci tree in structure, and as such the number of nodes in it is $$2^{O(k)}$$, which implies $$\Omega( \log n )$$ gap.
Since there is a simple algorithm that gets $$O( \log n)$$ approximation to coloring of rectangles, this might be tight. I don't know.