Is set packing easier when the sets are squares?

I am interested in the following problem:

There are n collections of M axis-parallel squares (not necessarily disjoint).
Pick a single square from each collection,
such that the n selected squares are pairwise interior-disjoint.

One way to approach the problem is to discretize the squares such that each square becomes a set of small squares. This makes the problem an instance of the following set packing problem:

There are n collections of sets (not necessarily disjoint).
Pick a single set from each collection,
such that the n selected sets are pairwise disjoint.

The set packing problem is equivalent to the independent set problem, and both are known to be NP-complete.

My question is: does the fact that the sets in this case are discretizations of axis-parallel squares make the problem any easier?

Particularly, is it possible to solve the problem, or at least approximate it to a constant factor, in time polynomial in $n$ (the number of collections), assuming $M$ is constant?

migrated from mathoverflow.netDec 23 '13 at 15:53

This question came from our site for professional mathematicians.

• Thanks! What about approximation to a constant factor? The general set packing problem cannot be approximated to a constant factor in polynomial time (unless $P=NP$). Does it become possible when the sets are squares? – Erel Segal-Halevi Dec 25 '13 at 16:00