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?
[Math] Best fit for multiple shapes inside an area
discrete geometrymg.metric-geometryoc.optimization-and-controlpacking-and-covering
Related Solutions
There's a fair bit of literature about efficient packing of squares in squares. See, e.g., Kearney and Shiu, Efficient packing of unit squares in a square, available at http://www.emis.de/journals/EJC/Volume_9/PDF/v9i1r14.pdf, also Walter Stromquist, Packing 10 or 11 unit squares in a square, available at http://www.combinatorics.org/Volume_10/PDF/v10i1r8.pdf
I have rewritten the post so that the proof is correct.
This problem is a bit hard, but following the Polya dictum, here is the answer to an apparently easier one: yes, if circles are replaced with parallel squares, and moreover, a suitable version of the greedy algorithm works.
Theorem. Let R be an $a$ by $b$ rectangle with $b\leq a\leq 2b.$ Any set of squares of total area at most $ab/2$ can be packed into R. (All rectangles and squares are assumed to be oriented parallel to the coordinate axes throughout.)
Corollary 1. A finite set of squares of total area 1 can be packed into a square of area 2.
Corollary 2. A finite set of circles of total area 1 can be packed into a circle of area 4.
Proof of Corollary 2. Replace each circle of diameter $d$ with a square of size $d$. Pack the squares into a square of double their total area, then circumscribe a circle C around it. The inscribed circles of the small squares have given radii, disjoint interiors, and the area of C is four times the total area of the given circles. $\square$
Proof of Theorem. The proof is by induction on the number of squares and uses the Packing Lemma below. Suppose that the largest square has size $c.$ Since $c^2\leq ab/2\leq b^2,$ we get $c\leq b.$ Split the rectangle R into two rectangles R' and R'' of the same height $b$ and of widths $c$ and $a-c$.
Case 1. If $c\leq a-b/2$ then the dimensions of the right rectangle R'' satisfy the conditions of the theorem, because $b/2\leq a-c\leq 2b.$ By the Packing Lemma, at least half the area of the left rectangle R' can be packed, starting with the $c$ square. The remaining squares are fewer in number and constitute at most half the area of R''. By the inductive assumption, they can be packed into R''.
Case 2. If $c\geq a-b/2$ then $b\geq 2(a-c)$ and R'' contains a subrectangle R''' of height $2(a-c)$ and width $a-c$, to which the theorem applies. Pack the $c$ square into R'. Since $c^2+(a-c)^2\geq a^2/2\geq ab/2,$ the remaining squares have total area at most $(a-c)^2$ and can be packed into R''' by the inductive assumption. $\square$
Packing Lemma. Let R be a $c$ by $b$ rectangle, $c\leq b$, and F be a finite set of squares with the total area at least half the area of R and the largest square of size $c$. Then a subset of F containing the $c$ square can be packed into R so that it covers at least half the area of R.
Proof. Induction in the number of squares in F. Cut the rectangle R into a sequence of horizontal strips of width $c$, starting with the $c$ square at the top. The height of each subsequent strip is the size of the largest unused square, which is placed at the left end. By the inductive assumption, at least half of the strip, area-wise, can be packed with squares from F. Continue the process until the height of the remaining part of R ("the bottom strip") becomes less than $c$, and hence its area less than $c^2.$ At this point at least half of the area of the intermediate strips has been covered, as well as the larger of the areas of the top and the bottom strip, so that at least half of R has been covered. $\square$
Comment: In the initial post, I said that the Packing Lemma easily implied the result for packing the square: order the squares by size and successively apply the lemma to pack vertical columns whose widths are determined by the largest square not yet packed, starting with the largest. While that argument had virtues of simplicity and presentability, it had an unfortunate drawback of being invalid. The columns are getting skinnier, so it may well happen that passing to the next column, the largest remaining square is too wide to fit, even though its area is a tiny proportion of the remaining area. Specific example: if one attempts to pack the squares of sizes 1/2, 1/3, 1/6+$\epsilon$, 1/6+$\epsilon$, 1/6 into the square of size $2\sqrt{2}/3+\epsilon<1$ following the naive algorithm then the first column has width 1/2 and contains the 1/2 square, the second column has width 1/3 and contains the next 3 squares (covering at least half the area in both cases), which leaves a narrow vertical strip of width less than 1/6 that cannot accommodate the remaining 1/6 square. By controlling the distortion (the ratio of width and height), we get a more natural result.
Best Answer
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."