23
$\begingroup$

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). 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.

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mohammad Al-Turkistany Mar 18 '11 at 9:27
  • $\begingroup$ 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. $\endgroup$ – Raphael Mar 18 '11 at 10:31
  • 9
    $\begingroup$ You can apply an affine transformation to make all the rectangles $1 \times 1$. So the problem is equivalent to that of packing squares. $\endgroup$ – Peter Shor Mar 18 '11 at 10:54
  • 1
    $\begingroup$ @turkistany: Would you give me a reference that shows the NP-completeness for 1x3 rectangles? Or, is it easy to observe? $\endgroup$ – Yoshio Okamoto Mar 18 '11 at 12:54
  • 3
    $\begingroup$ By searching based on Peter Shor's observation 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). $\endgroup$ – Raphael Mar 18 '11 at 14:55
12
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Raphael Mar 19 '11 at 9:14
  • 1
    $\begingroup$ 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... $\endgroup$ – Sariel Har-Peled Mar 19 '11 at 20:44
2
$\begingroup$

These two papers address your problem:

E. G. Birgin and R. D. Lobato, "Orthogonal packing of identical rectangles within isotropic convex regions", 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", Computers & Operations Research 33, pp. 3535-3548, 2006.

 

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – András Salamon Mar 18 '11 at 12:50
  • 3
    $\begingroup$ 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. $\endgroup$ – Peter Shor Mar 18 '11 at 15:27
  • 4
    $\begingroup$ 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. $\endgroup$ – Peter Shor Mar 18 '11 at 16:56
  • 2
    $\begingroup$ 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? $\endgroup$ – Raphael Mar 18 '11 at 17:38
  • 3
    $\begingroup$ @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. $\endgroup$ – Peter Shor Mar 18 '11 at 19:22
1
$\begingroup$

Peter Shor observed 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 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)

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 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.)

|cite|improve this answer
$\endgroup$
  • 5
    $\begingroup$ Looking at the paper, from the diagrams it appears that the squares to be packed are not all equal size. $\endgroup$ – Peter Shor Mar 18 '11 at 13:46
  • 1
    $\begingroup$ @Peter: You are right, this paper does not imply anything about Raphaël's problem. $\endgroup$ – András Salamon Mar 18 '11 at 14:57
0
$\begingroup$

Maybe this paper can be of interest for you :

Tiling a polygon with rectangles by Kenyon & Kenyon in FOCS 92.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Mar 18 '11 at 11:00
  • $\begingroup$ indeed, this is not the same problem, my mistake. $\endgroup$ – Sylvain Peyronnet Mar 18 '11 at 11:13
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ This sounds plausible. Note that Raphaël provided a link in a comment maven.smith.edu/~orourke/TOPP/P56.html with a pointer to a paper with the actual reduction. $\endgroup$ – András Salamon Mar 19 '11 at 21:48
  • $\begingroup$ Oh, I have not noticed, thx. $\endgroup$ – domotorp Mar 20 '11 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.