Welcome to MathOverflow

Question

1

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?

flag	asked Mar 31 2010 at 10:20 jonpauldavies 11●2

	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? – Douglas Zare Mar 31 2010 at 10:39
	no, multiple different rectangular shapes. no rotations. thanks for the comment. – jonpauldavies Mar 31 2010 at 10:59
	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?" – Vectornaut Apr 12 2010 at 2:28
	@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). – Gerry Myerson Apr 12 2010 at 4:41

Gerry Myerson · Answer 1 · 2010-03-31 11:51:59Z UTC

2

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

Gerry Myerson
15.7k●1●47●87

@Gerry I think the problem you stated isn't bin-packing, but rather the integer knapsack problem which is solvable in polynomial time. – Mio Mar 31 2010 at 12:18

@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. – Gerry Myerson Mar 31 2010 at 22:16

@Gerry sure, here's a site outlining the dynamic programming solution for integer knapsack cgm.cs.mcgill.ca/~msuder/courses/360/lectures/… – Mio Apr 1 2010 at 8:06

@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)? – Gerry Myerson Apr 9 2010 at 7:25

1

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/… – François G. Dorais♦ Apr 12 2010 at 5:02

Gerry Myerson · Answer 2 · 2010-04-12 01:32:14Z UTC

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.

Best fit for multiple shapes inside an area

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.