Is there a forumla to come up with the best fit for multiple shapes inside a rectangular area, so that none of the shapes are overlapping?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Do you mean you want to pack as many copies of a single shape into the rectangle as possible? Do you allow rotations and reflections or just translations? $\endgroup$– Douglas ZareCommented Mar 31, 2010 at 10:39
-
$\begingroup$ no, multiple different rectangular shapes. no rotations. thanks for the comment. $\endgroup$– user5052Commented Mar 31, 2010 at 10:59
-
$\begingroup$ I think this question would be easier to answer if I could understand what is being asked. Is the following an accurate interpretation? "We have a set of rectangular shapes, and a rectangular area. We want to fit as many of the shapes as possible inside the area. We are not allowed to rotate the shapes. Is there an algorithm for doing this?" $\endgroup$– VectornautCommented Apr 12, 2010 at 2:28
-
$\begingroup$ @Vectornaut, I can't speak for jonpauldavies, but I think the question is as you have stated, except that one wants to fill up as much of the rectangular area as possible (which may not be the same thing as using as many of the shapes as possible, since the shapes are different). $\endgroup$– Gerry MyersonCommented Apr 12, 2010 at 4:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
No. There isn't even a formula for best fit of rectangles of integer height and width 1 inside a rectangle of width 1. See "bin-packing."
answered Mar 31, 2010 at 11:51
-
$\begingroup$ @Gerry I think the problem you stated isn't bin-packing, but rather the integer knapsack problem which is solvable in polynomial time. $\endgroup$– MioCommented Mar 31, 2010 at 12:18
-
$\begingroup$ @Mio, news to me. Do you have a reference for solvability in polynomial time? Maybe "subset sum" problem is a better description for the problem I stated. $\endgroup$ Commented Mar 31, 2010 at 22:16
-
$\begingroup$ @Gerry sure, here's a site outlining the dynamic programming solution for integer knapsack cgm.cs.mcgill.ca/~msuder/courses/360/lectures/… $\endgroup$– MioCommented Apr 1, 2010 at 8:06
-
$\begingroup$ @Mio, thanks, but I'm confused. According to my reading of Garey and Johnson, Subset Sum is NP-complete. This problem goes, given a finite (multi-)set A of positive integers, and another positive integer B, determine whether there's a subset of A whose elements sum to B. I don't see how there can be a polynomial time algorithm for the "best fit of rectangles" problem I stated if Subset Sum is NP-complete (in the absence of a proof that P = NP, that is)? $\endgroup$ Commented Apr 9, 2010 at 7:25
-
3$\begingroup$ Gerry and Mio are both correct, in a way... The dynamic algorithm is pseudo-polynomial time and the knapsack problem is NP complete. The difference is how you measure the complexity of the question. This is discussed on Wikipedia - en.wikipedia.org/wiki/Knapsack_problem#Computational_complexity $\endgroup$ Commented Apr 12, 2010 at 5:02
$\begingroup$
$\endgroup$
1
Where is everybody? Only one answer, which hasn't received any upvotes, nor any downvotes. I don't know any way to put this problem back on the radar screen other than posting an answer to it, so here's an extended version of the answer I already posted.
Garey and Johnson, Computers and Intractability, has a list of problems that are known to be NP-complete. Subset Sum is problem SP13 in that list, on page 223 of the book. I quote:
Instance: Finite set $A$, size $s(a)\in{\bf Z}^+$ for each $a\in A$, positive integer $B$.
Question: Is there a set $A'\subseteq A$ such that the sum of the sizes of the elements in $A'$ is exactly $B$?
Now let's look at a special case of the current MO question. Suppose that the multiple shapes are rectangles with base 1 and various integer heights, and the (big) rectangular area also has base 1 and integer height B. Suppose that there is an efficient way to determine the best fit of the shapes in the big rectangle (I am reinterpreting the original request for a "formula" as a request for an efficient method). Then you have an efficient way to solve Subset Sum. Namely, apply the alleged efficient best fit method to the data. If it finds a way to completely fill the big rectangle, then it has found a subset summing to $B$, and if it doesn't find a way to completely fill the big rectangle, then it has proved that there is no subset summing to $B$.
It follows that there is no efficient method for finding a best fit in this special case of the original problem, unless P = NP.
answered Apr 12, 2010 at 1:32
-
$\begingroup$ Does it reduce to a 2D vector sum problem in general, or does the complexity of overlap completely trump this approach? $\endgroup$ Commented Apr 12, 2010 at 5:05