<p>The problem can be reformulated as picking a maximum number of points inside a convex polygon, such that the every pair of them is in distance (under the $L_\infty$ metric) at least $1$ from each other (just think about the centers of the squares). This in turn is related to the same problem where one uses the regular Euclidean distance. This is in turn related to meshing, where one is interested in breaking a polygon into nicely behaved regions (i.e., you take the Voronoi diagram of the centers [see Centroidal Voronoi tessellations]).</p>

<p>Anyway, a $(1-\epsilon)$-approximation is quite easy. You randomly slide a grid of sidelength $O(1/\epsilon)$. Clip the polygon into the grid, and solve the problem inside each piece of intersection of the polygon with the grid using brute force. An algorithm with running time $O(M*noise(\epsilon))$ should easily follow, where $M$ is the number of points (i.e., rectangles), and $noise(\epsilon)$ is some horrendous function that depends only on $\epsilon$. </p>

CC BY-SA 2.5
2011-03-19T09:14:33.627Z
Thanks. Am I right in thinking that even in the case where we have a polynomial bound on the number of rectangles/squares, it still is not clear if the problem is in P?
Simd
CC BY-SA 2.5
2011-03-19T20:44:23.550Z
Here is my 2 cents of guessing/speculating...It would be surprising if it is in P - you would need to show some extra properties of the optimal solution. However, my guess would be that a formal proof of NP-hardness is out of reach - the problem has too much structure. Feder and Greene showed that the k-center clustering is NP-hard to approximate within a certain factor. I think/speculate that their proof can be used to prove that the above problem is NP-Hard if the polygon has holes...
Sariel Har-Peled
CC BY-SA 2.5
2011-03-18T19:42:17.633Z
2011-03-19T06:02:21.217Z
2011-03-19T06:02:21.217Z
Sariel Har-Peled
<p>These two papers address your problem:</p>

<p>E. G. Birgin and R. D. Lobato, "<a href="http://www.ime.usp.br/~egbirgin/publications/bl.pdf" rel="nofollow">Orthogonal packing of identical rectangles within isotropic convex regions</a>", Computers &amp; Industrial Engineering 59, pp. 595-602, 2010. </p>

<p>E. G. Birgin, J. M. Martínez, F. H. Nishihara and D. P. Ronconi, "<a href="http://www.ime.usp.br/~egbirgin/publications/bmnr.pdf" rel="nofollow">Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization</a>", Computers &amp; Operations Research 33, pp. 3535-3548, 2006.</p>

<p> </p>

CC BY-SA 2.5
2011-03-18T12:50:46.107Z
These papers look at solving the problem in practice.  As far as I can tell, the question is asking whether the problem is known to be NP-hard.
András Salamon
CC BY-SA 2.5
2011-03-18T15:08:09.460Z
Or even in NP. That's not immediately obvious to me either to be honest but I am sure a computational geometer would know more on that front.
Simd
CC BY-SA 2.5
2011-03-18T15:27:10.670Z
It's fairly easy to show it's in NP. Suppose I give you a diagram of the optimal packing which tells you which squares are touching which sides of the polygon, and which squares are above/below/left/right of other squares. The question of whether you can find the coordinates for a set of squares which pack in exactly that way is a linear program, and so you can verify that this is a diagram for a feasible packing.
Peter Shor 
CC BY-SA 2.5
2011-03-18T16:38:55.670Z
Good point. My concern was about what precision you would need to be able to do that to make the problem formally in NP (i.e. could you implement it in Turing machine?) but it's in no way as interesting as the main question of course :)
Simd
CC BY-SA 2.5
2011-03-18T16:56:48.940Z
If all the vertices of your polygon are integers (or rationals), a standard result on linear programs says that you don't need more than a polynomial amount of extra precision, and the linear program can be solved exactly in polynomial time. Apologies if you already knew that, but I can't tell from your comment above -- and even if you did, some people won't.
Peter Shor 
CC BY-SA 2.5
2011-03-18T17:38:02.093Z
Thanks.  I did know that once but it was good to be reminded. It also seems you could have an exponential number of squares packed in the polygon so I am not sure you can afford to actually list them all.  Maybe there is some scaling you can do to get round this?
Simd
CC BY-SA 2.5
2011-03-18T19:22:25.553Z
@Rafael: I was assuming (without justification) that you had a polynomial bound on the number of squares. If you allow exponential size polygons, things get much trickier.
Peter Shor 
CC BY-SA 2.5
2011-03-18T12:26:57.400Z
2011-03-18T12:26:57.400Z
Marcus Ritt
<p>Peter Shor observed that by rescaling, this problem becomes about packing unit squares into a convex polygon.</p>

<p><em>Edit: the remainder of this answer does not apply, as it drops the explicitly stated requirement that the shapes to be packed are all the same size.</em></p>

<hr>

<p>The related question <a href="https://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem">NP-Hardness of a special case of orthogonal packing problem</a> mentions a paper with the result needed for the first question:</p>

<ul>
<li><em>Packing squares into a square,</em> Joseph Y-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin, Journal of Parallel and Distributed Computing <strong>10</strong> 271–275. (<a href="http://dx.doi.org/10.1016/0743-7315%2890%2990019-L" rel="nofollow noreferrer">link</a>)</li>
</ul>

<p>From the paper:</p>

<blockquote>
  <p>we show that the square packing problem is strongly
  NP-complete by reducing the 3-partition problem to it.</p>
</blockquote>

<p>Hence the problem is NP-hard even for the special case where the rectangles to be packed are <a href="http://en.wikipedia.org/wiki/Similarity_%28geometry%29" rel="nofollow noreferrer">similar</a> to the container.  (Unlike the authors of this paper, I am not completely convinced that the problem is in NP, since the positions might have to be specified to a large amount of precision, which may cause the verification to no longer be polynomial in the input size.)</p>

CC BY-SA 2.5
2011-03-18T13:46:47.777Z
Looking at the paper, from the diagrams it appears that the squares to be packed are not all equal size.
Peter Shor 
CC BY-SA 2.5
2011-03-18T14:57:32.097Z
@Peter: You are right, this paper does not imply anything about Raphaël's problem.
András Salamon
CC BY-SA 2.5
2011-03-18T12:43:48.707Z
2011-03-18T15:00:37.460Z
2017-04-13T12:32:28.077Z
András Salamon
<p>If the polygon into which you want to pack is not necessarily convex, then I think the problem becomes NP-hard. Here is a very sketchy proof. The reduction is from some Planar-3-SAT type problem. To each variable you can have a 1.1 x 1 place, depending where in this area you place one square will determine whether your variable is true of false. Also, if you leave .1 area left/right, then you can move two other squares a little more inside, and also the ones behind them, eventually giving another .1 free space somewhere else that together now affect four squares and so on. After you have as many copies as the occurrences of the respective literal, you connect these tubes to the respective clause component and there again use some similar gadget to ensure that from the three ingoing tubes at least one has to have a .1 extra space.</p>

CC BY-SA 2.5
2011-03-19T21:48:30.090Z
This sounds plausible.  Note that Raphaël provided a link in a comment http://maven.smith.edu/~orourke/TOPP/P56.html with a pointer to a paper with the actual reduction.
András Salamon
CC BY-SA 2.5
2011-03-20T06:33:43.413Z
Oh, I have not noticed, thx.
domotorp
CC BY-SA 2.5
2011-03-19T17:58:48.123Z
2011-03-19T17:58:48.123Z
domotorp
<p>Maybe this paper can be of interest for you :</p>

<p><a href="http://www.math.brown.edu/~rkenyon/papers/rectiles.ps" rel="nofollow">Tiling a polygon with rectangles</a> by Kenyon &amp; Kenyon in FOCS 92.</p>

CC BY-SA 2.5
2011-03-18T11:00:21.780Z
Thanks. However if I understand correctly, a tiling covers the polygon exactly. This will almost never be possible in my case (consider an arbitrary triangle at some arbitrary orientation) which seems to make my optimisation problem fundamentally different.
Simd
CC BY-SA 2.5
2011-03-18T11:13:38.837Z
indeed, this is not the same problem, my mistake.
Sylvain Peyronnet
CC BY-SA 2.5
2011-03-18T10:34:18.090Z
2011-03-18T10:34:18.090Z
Sylvain Peyronnet
<p>I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps.  In my problem you are not allowed to rotate the rectangles and can assume that they are oriented parallel with the axes. You are just given the dimensions of a rectangle and the vertices of the polygon and asked how many identical copies of the rectangle can be packed into the polygon.  If you are allowed to rotate the rectangles this problem is known to be NP-hard I believe. However, what is known if you cannot? How about if the convex polygon is simply a triangle?  Are there known approximation algorithms if the problem is indeed NP-hard? </p>

<p>Summary so far (21 March '11). Peter Shor observes that we can regard this problem as one of packing unit squares in a convex polygon and that that problem is in NP if you impose a polynomial bound on the number of squares/rectangles to be packed.  Sariel Har-Peled points out there is a PTAS for the same polynomially bounded case.  However, in general the number of squares packed can be exponential in the size of the input which only consists of a possibly short list of pairs of integers.  The following questions appear to be open.</p>

<p>Is the full unbounded version in NP?
Is there a PTAS for the unbounded version?
Is the polynomially bounded case in P or NPC? And my personal favourite, is the problem any easier if you just restrict yourself to packing unit squares into a triangle?</p>

CC BY-SA 2.5
2011-03-18T09:27:38.677Z
Packing with 1x3 rectangles is NP-complete (with rotation) and I guess it becomes easy if we disallow rotations. You find the maximum number of rectangles for each row (or columns) and add them to get the overall maximum number of packed rectangles.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-03-18T10:31:54.490Z
I am not sure fixing the dimensions to be 1x3 (or anything else) helps too much for my problem does it? The convex polygon does not necessarily have any sides parallel to the axes and you still need to decide where to put the rectangles.  You could place them lowest in the y-axis first then justified to the left as a reasonable heuristic but you can construct examples fairly easily where this is not optimal.
Simd
CC BY-SA 2.5
2011-03-18T10:54:51.040Z
You can apply an affine transformation to make all the rectangles $1 \times 1$. So the problem is equivalent to that of packing squares.
Peter Shor 
CC BY-SA 2.5
2011-03-18T12:54:11.853Z
@turkistany: Would you give me a reference that shows the NP-completeness for 1x3 rectangles?  Or, is it easy to observe?
Yoshio Okamoto
CC BY-SA 2.5
2011-03-18T14:55:47.960Z
By searching based on Peter Shor's observation http://maven.smith.edu/~orourke/TOPP/P56.html comes up which is interesting. However it appears to be focussed on general simple polygons (i.e. they can be concave).
Simd
<reference-request><np-hardness><cg.comp-geom><optimization><packing>
Packing rectangles into convex polygons but without rotations
Simd
# Packing rectangles into convex polygons but without rotations

(Asked by: username_0 on 2011-03-17)

I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps. In my problem you are not allowed to rotate the rectangles and can assume that they are oriented parallel with the axes. You are just given the dimensions of a rectangle and the vertices of the polygon and asked how many identical copies of the rectangle can be packed into the polygon. If you are allowed to rotate the rectangles this problem is known to be NP-hard I believe. However, what is known if you cannot? How about if the convex polygon is simply a triangle? Are there known approximation algorithms if the problem is indeed NP-hard?

Summary so far (21 March '11). username_2observes that we can regard this problem as one of packing unit squares in a convex polygon and that that problem is in NP if you impose a polynomial bound on the number of squares/rectangles to be packed. username_4 points out there is a PTAS for the same polynomially bounded case. However, in general the number of squares packed can be exponential in the size of the input which only consists of a possibly short list of pairs of integers. The following questions appear to be open.

Is the full unbounded version in NP?
Is there a PTAS for the unbounded version?
Is the polynomially bounded case in P or NPC? And my personal favourite, is the problem any easier if you just restrict yourself to packing unit squares into a triangle?

**Tags:** reference-request, np-hardness, cg.comp-geom, optimization, packing

> **Comments:**
> **username_1**: Packing with 1x3 rectangles is NP-complete (with rotation) and I guess it becomes easy if we disallow rotations. You find the maximum number of rectangles for each row (or columns) and add them to get the overall maximum number of packed rectangles.  
> **username_0**: I am not sure fixing the dimensions to be 1x3 (or anything else) helps too much for my problem does it? The convex polygon does not necessarily have any sides parallel to the axes and you still need to decide where to put the rectangles.  You could place them lowest in the y-axis first then justified to the left as a reasonable heuristic but you can construct examples fairly easily where this is not optimal.  
> **username_2**: You can apply an affine transformation to make all the rectangles $1 \times 1$. So the problem is equivalent to that of packing squares.  
> **username_3**: @turkistany: Would you give me a reference that shows the NP-completeness for 1x3 rectangles?  Or, is it easy to observe?  
> **username_0**: By searching based on Peter Shor's observation http://maven.smith.edu/~orourke/TOPP/P56.html comes up which is interesting. However it appears to be focussed on general simple polygons (i.e. they can be concave).  

---

## 5 answers

### Answer by username_4 on 2011-03-18. Score: 12

The problem can be reformulated as picking a maximum number of points inside a convex polygon, such that the every pair of them is in distance (under the $L\_\infty$ metric) at least $1$ from each other (just think about the centers of the squares). This in turn is related to the same problem where one uses the regular Euclidean distance. This is in turn related to meshing, where one is interested in breaking a polygon into nicely behaved regions (i.e., you take the Voronoi diagram of the centers [see Centroidal Voronoi tessellations]).

Anyway, a $(1-\epsilon)$-approximation is quite easy. You randomly slide a grid of sidelength $O(1/\epsilon)$. Clip the polygon into the grid, and solve the problem inside each piece of intersection of the polygon with the grid using brute force. An algorithm with running time $O(M\*noise(\epsilon))$ should easily follow, where $M$ is the number of points (i.e., rectangles), and $noise(\epsilon)$ is some horrendous function that depends only on $\epsilon$.

> **Comments:**
> **username_0**: Thanks. Am I right in thinking that even in the case where we have a polynomial bound on the number of rectangles/squares, it still is not clear if the problem is in P?  
> **username_4**: Here is my 2 cents of guessing/speculating...It would be surprising if it is in P - you would need to show some extra properties of the optimal solution. However, my guess would be that a formal proof of NP-hardness is out of reach - the problem has too much structure. Feder and Greene showed that the k-center clustering is NP-hard to approximate within a certain factor. I think/speculate that their proof can be used to prove that the above problem is NP-Hard if the polygon has holes...  

---

### Answer by username_5 on 2011-03-18. Score: 2

These two papers address your problem:

E. G. Birgin and R. D. Lobato, "[Orthogonal packing of identical rectangles within isotropic convex regions](http://www.ime.usp.br/~egbirgin/publications/bl.pdf)", Computers & Industrial Engineering 59, pp. 595-602, 2010.

E. G. Birgin, J. M. Martínez, F. H. Nishihara and D. P. Ronconi, "[Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization](http://www.ime.usp.br/~egbirgin/publications/bmnr.pdf)", Computers & Operations Research 33, pp. 3535-3548, 2006.

> **Comments:**
> **username_6**: These papers look at solving the problem in practice.  As far as I can tell, the question is asking whether the problem is known to be NP-hard.  
> **username_0**: Or even in NP. That's not immediately obvious to me either to be honest but I am sure a computational geometer would know more on that front.  
> **username_2**: It's fairly easy to show it's in NP. Suppose I give you a diagram of the optimal packing which tells you which squares are touching which sides of the polygon, and which squares are above/below/left/right of other squares. The question of whether you can find the coordinates for a set of squares which pack in exactly that way is a linear program, and so you can verify that this is a diagram for a feasible packing.  
> **username_0**: Good point. My concern was about what precision you would need to be able to do that to make the problem formally in NP (i.e. could you implement it in Turing machine?) but it's in no way as interesting as the main question of course :)  
> **username_2**: If all the vertices of your polygon are integers (or rationals), a standard result on linear programs says that you don't need more than a polynomial amount of extra precision, and the linear program can be solved exactly in polynomial time. Apologies if you already knew that, but I can't tell from your comment above -- and even if you did, some people won't.  
> **username_0**: Thanks.  I did know that once but it was good to be reminded. It also seems you could have an exponential number of squares packed in the polygon so I am not sure you can afford to actually list them all.  Maybe there is some scaling you can do to get round this?  
> **username_2**: @Rafael: I was assuming (without justification) that you had a polynomial bound on the number of squares. If you allow exponential size polygons, things get much trickier.  

---

### Answer by username_6 on 2011-03-18. Score: 1

username_2observed that by rescaling, this problem becomes about packing unit squares into a convex polygon.

*Edit: the remainder of this answer does not apply, as it drops the explicitly stated requirement that the shapes to be packed are all the same size.*

---

The related question [NP-Hardness of a special case of orthogonal packing problem](https://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem) mentions a paper with the result needed for the first question:

* *Packing squares into a square,* Joseph Y-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin, Journal of Parallel and Distributed Computing **10** 271–275. ([link](http://dx.doi.org/10.1016/0743-7315%2890%2990019-L))

From the paper:

> we show that the square packing problem is strongly
> NP-complete by reducing the 3-partition problem to it.

Hence the problem is NP-hard even for the special case where the rectangles to be packed are [similar](http://en.wikipedia.org/wiki/Similarity_%28geometry%29) to the container. (Unlike the authors of this paper, I am not completely convinced that the problem is in NP, since the positions might have to be specified to a large amount of precision, which may cause the verification to no longer be polynomial in the input size.)

> **Comments:**
> **username_2**: Looking at the paper, from the diagrams it appears that the squares to be packed are not all equal size.  
> **username_6**: @Peter: You are right, this paper does not imply anything about Raphaël's problem.  

---

### Answer by username_7 on 2011-03-19. Score: 0

If the polygon into which you want to pack is not necessarily convex, then I think the problem becomes NP-hard. Here is a very sketchy proof. The reduction is from some Planar-3-SAT type problem. To each variable you can have a 1.1 x 1 place, depending where in this area you place one square will determine whether your variable is true of false. Also, if you leave .1 area left/right, then you can move two other squares a little more inside, and also the ones behind them, eventually giving another .1 free space somewhere else that together now affect four squares and so on. After you have as many copies as the occurrences of the respective literal, you connect these tubes to the respective clause component and there again use some similar gadget to ensure that from the three ingoing tubes at least one has to have a .1 extra space.

> **Comments:**
> **username_6**: This sounds plausible.  Note that Raphaël provided a link in a comment http://maven.smith.edu/~orourke/TOPP/P56.html with a pointer to a paper with the actual reduction.  
> **username_7**: Oh, I have not noticed, thx.  

---

### Answer by username_8 on 2011-03-18. Score: 0

Maybe this paper can be of interest for you :

[Tiling a polygon with rectangles](http://www.math.brown.edu/~rkenyon/papers/rectiles.ps) by Kenyon & Kenyon in FOCS 92.

> **Comments:**
> **username_0**: Thanks. However if I understand correctly, a tiling covers the polygon exactly. This will almost never be possible in my case (consider an arbitrary triangle at some arbitrary orientation) which seems to make my optimisation problem fundamentally different.  
> **username_8**: indeed, this is not the same problem, my mistake.  

---

