I have come across the following optimisation subproblem:

Geometric Disjoint Set Cover. Consider a collection $C$ of (not necessarily distinct) ranges taken from a universe range $X \subset \mathbb{R}^d$. Does there exist a $k$-partition of $C$ into set covers of $X$?

I am particularly interested in the case where ranges are axis-parallel rectangles in $\mathbb{R}^2$, and $k$ is small. Does there exist a polynomial time algorithm for fixed $k$ and $d$? Is there a more widely known name I can search by?

Without the geometric constraint, this problem is NP-hard even for $k = 2$, by equivalence to deciding $2$-colourability for hypergraphs. On the other hand, when $d = 1$ there is a simple greedy $O(|C| \log |C|)$ algorithm that works for all $k$: at each step consume up to the $k$-th rightmost endpoint of intervals starting at or before the current position. Can this be generalised to $d = 2$?



Your Answer

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