<p>I think your problem is NP-complete already for M=3, as there is a quite straight-forward reduction to it from 3SAT. Just for each variable xi, make a pair of squares, truei and falsei. For a clause Cj, make a pair of squares for each of its literals, e.g., Aj1, Bj1, Aj2, Bj2, Aj3, Bj3. Let Aj1 intersect the respective square of the variable (e.g., truei) (but disjoint from any other similar clause-squares intersecting it), while the Bj1, Bj2 and Bj3 are put somewhere in a disjoint way. Finally, for each clause we have a collection of three squares, which is also Bj1, Bj2 and Bj3.</p>

CC BY-SA 3.0
2013-12-24T14:20:36.720Z
I don't see why you need a pair of squares for each of the literals of a clause. Can't you simply have a set containing 2 big squares for each variable, and a set containing three little squares for each clause? The little square you choose for each clause will force the variable to take on the correct value.
Peter Shor 
CC BY-SA 3.0
2013-12-24T18:22:51.203Z
@Peter: Of course, you are correct. First I wanted to prove it with M=2, but then I thought it does not matter, so I picked M=3 and simplified things, apparently not enough.
domotorp
CC BY-SA 3.0
2013-12-24T18:43:42.760Z
Can't M=2 can be solved in polynomial time? The relations between the squares are pairwise, so when M=2, all the constraints are pairwise, yielding an instance of 2-SAT, which is polynomial.
Peter Shor 
CC BY-SA 3.0
2013-12-24T20:34:31.397Z
Of course, again you are correct. That explains why I did not manage with M=2...
domotorp
CC BY-SA 3.0
2013-12-25T16:00:02.593Z
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
CC BY-SA 3.0
2013-12-25T17:43:36.723Z
What are you trying to approximate? The maximum possible number of collections such that you can pick an element from each in a disjoint way?
domotorp
CC BY-SA 3.0
2013-12-31T05:45:22.473Z
@domotorp good question. I have to think about it.
Erel Segal-Halevi
CC BY-SA 3.0
2013-12-23T21:16:57.000Z
2013-12-23T21:16:57.000Z
domotorp
<p>I am interested in the following problem:</p>

<pre><code>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.
</code></pre>

<p>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 <strong><a href="https://en.wikipedia.org/wiki/Set_packing" rel="nofollow">set packing</a></strong> problem:</p>

<pre><code>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.
</code></pre>

<p>The set packing problem is equivalent to the <strong><a href="https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29" rel="nofollow">independent set</a></strong> problem, and both are known to be NP-complete.</p>

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

<p>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? </p>

<ds.algorithms><packing>
Is set packing easier when the sets are squares?
Erel Segal-Halevi
# Is set packing easier when the sets are squares?

(Asked by: username_0 on 2013-12-09)

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?

**Tags:** ds.algorithms, packing


---

## 1 answers

### Answer by username_1 on 2013-12-23. Score: 3 | Accepted answer

I think your problem is NP-complete already for M=3, as there is a quite straight-forward reduction to it from 3SAT. Just for each variable xi, make a pair of squares, truei and falsei. For a clause Cj, make a pair of squares for each of its literals, e.g., Aj1, Bj1, Aj2, Bj2, Aj3, Bj3. Let Aj1 intersect the respective square of the variable (e.g., truei) (but disjoint from any other similar clause-squares intersecting it), while the Bj1, Bj2 and Bj3 are put somewhere in a disjoint way. Finally, for each clause we have a collection of three squares, which is also Bj1, Bj2 and Bj3.

> **Comments:**
> **username_2**: I don't see why you need a pair of squares for each of the literals of a clause. Can't you simply have a set containing 2 big squares for each variable, and a set containing three little squares for each clause? The little square you choose for each clause will force the variable to take on the correct value.  
> **username_1**: @Peter: Of course, you are correct. First I wanted to prove it with M=2, but then I thought it does not matter, so I picked M=3 and simplified things, apparently not enough.  
> **username_2**: Can't M=2 can be solved in polynomial time? The relations between the squares are pairwise, so when M=2, all the constraints are pairwise, yielding an instance of 2-SAT, which is polynomial.  
> **username_1**: Of course, again you are correct. That explains why I did not manage with M=2...  
> **username_0**: 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?  
> **username_1**: What are you trying to approximate? The maximum possible number of collections such that you can pick an element from each in a disjoint way?  
> **username_0**: @username_1 good question. I have to think about it.  

---

