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?