Author |
Topic: A Meta Packing Problem (Read 1082 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
A Meta Packing Problem
« on: Aug 30th, 2004, 1:40pm » |
 Quote  Modify
|
We define the self-packing efficiency for a given shape as the largest value [phi] such that any number N of unit-volume pieces of this shape can be packed within a container of the same shape with volume N/[phi].
Simple, symmetric 2-D shapes like circles, squares and equilateral triangles all have a self-packing efficiency of 1/2.
Can one define 2-D shapes with a higher self-packing efficiency? What is the highest possible self-packing efficiency in 2-D? What is the associated shape?
And what about 3-D?
Questions, questions...
Hint: ::It is relatively straightforward to reach a 2-D self-packing efficiency of 1/[sqrt]2. Can you improve upon this? Or - alternatively - can you demonstrate this is the maximum value for 2-D?::
|
| « Last Edit: Aug 30th, 2004, 2:13pm by JocK » |
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A Meta Packing Problem
« Reply #1 on: Aug 31st, 2004, 5:29am » |
Quote Modify
|
My answer for phi > 1/sqrt(2)
::
Let's consider the rectangle with proportion 1:sqrt(2). Normalized to area 1, it has sides a=sqrt(sqrt(1/2)) and b=sqrt(sqrt(2))
Let's write phi[n] as the highest possible packing density for n shapes. Phi is the maximum of these values.
- 2 such rectangles nicely combine into a new rectangle sqrt(2) times the size. phi[2] =1.
- 3 or 4 such rectangles can be arranged within a rectangle 2 times the size, or area 4. phi[3] = 0.75, phi[4] = 1.
- 5 such rectangles can be placed in a rectangle of size (a+b) x (3b). phi[5] = 5/((a+b)/a)^2 = 0.857864
- 6 to 8 such rectangles can be placed in a rectangle of size 2b x 4a and area 8. phi[6] = 6/8 = 0.75, phi[7], phi[8] are larger
- 9 rectangles can be arranged with density 1, like any square n.
- 10 rectanges can be arranged with the same density as 5, by combining the rectanges 2 by 2.
- 11 rectangles can be arranged in a rectangle of size 3a, 3b+a, with density phi[11] = 11/((3b+a)/b)^2 = 0.8004
- From 12 on, you can easily arrange n rectangles in a rectangle k*k where k=ceilsqrt(n)), the density remains above 0.75.
So, for the rectangle with proportion 1:sqrt(2), phi is 0.75.
In fact, it is optimal for rectangles, because you can not arrange 3 rectangles in a rectangle smaller than twice the size and 4 times the area. So 3/4 is the best you can do.
::
Probably a better packing can be obtained with the help of
::the Barnach-Tarski theorem  ::.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: A Meta Packing Problem
« Reply #2 on: Aug 31st, 2004, 12:43pm » |
Quote Modify
|
on Aug 31st, 2004, 5:29am, Grimbal wrote:.. you can not arrange 3 rectangles in a rectangle smaller than twice the size and 4 times the area. So 3/4 is the best you can do.
|
|
This is obviously not true. Take a rectangle with aspect ratio [sqrt]3. Three of these can be packed in a rectangle with the same aspect ratio and three times the area.
So this begs the question: Can you find a rectangle with self-packing efficiency larger than 3/4 ...?
What about 7/9 ? (Big hint!) 
|
| « Last Edit: Aug 31st, 2004, 1:03pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
I managed to find a packing with efficiency hinted by Jock. Below is a brief explanation of how I arrived at the solution. Needless to say, Grimbal’s solution was of a considerable help.
For those who doesn’t like to read long postings: Jock’s packing is possible for the rectangle with aspect ratio a2, where a [in] [0.8070…, 0.8091…].
Let the length of the smaller side of the rectangle be a < 1, and of the bigger side 1/a. Then, in the self-packing (SP) the aspect ratio of the enclosing rectangle should be 1:a2.
It is clear, that in efficient SP, at least one of the sides of the enclosing rectangle should be packed by the small rectangles without spare room (in the attached drawing, this side is always drawn horizontally). Therefore, one of the sides of the enclosed rectangle, S1, will always be of the form na + m/a, where n, m are nonnegative integers. Now, S1 may be the smaller or the bigger side of the enclosing rectangle.
In the first case, there always exists a rectangle S1xS2, with S1:S2 = a2, and its local efficiency [phi]’ = N/(S1S2), where N is the maximal number of small rectangles fitting in the big one. In the second case, the enclosing rectangle exists if n=0, or the small side S2 = S1a2 is big enough to enclose the length 1/a.
This may be put another way around: one may think about some self-packing pattern for a specific number of small rectangles N; that will give the pair n, m, and then find the bounds for the value a in order for the above conditions to be satisfied. Fortunatelly, this is not so difficult when N is small.
Here’s an example for N=3 (see the drawing). I choose n=3, m=0, so that S1 = 3a, and I consider it to be the bigger side of the enclosing rectangle. Then, in order for the small rectangle to fit into the big one, we must have S2 = 3a3 [ge] 1/a, that is a [ge] 4[sqrt](1/3). From the other hand, to meet Jock’s SP efficiency, we must have S1 S2 = 9a4 [le] 27/7, that is a [le] 4[sqrt](3/7).
In a similar manner, I’ve found the patterns and bounds for N=2,5,6 (clearly, N=4 trivially has a SP efficiency of 1, like any other perfect square number). And of course, N=7 is the “weakest link”, which establishes Jock’s efficiency.
Here’s the summary:
N = 2: n = 0, m = 2; smaller: 4[sqrt]( 7/18 ) [le] a [le] 4[sqrt](1/2).
N = 3: n = 3, m = 0; bigger: 4[sqrt]( 1/3 ) [le] a [le] 4[sqrt](3/7).
N = 5: n = 1, m = 1; smaller: [sqrt] [7/38 * ([sqrt](45/7) + 1)] [le] a [le] [sqrt][([sqrt]13 – 1) / 6].
N = 6: n = 4, m = 0; bigger: [sqrt] [([sqrt]17 – 1)/2] [le] a [le] 4 [sqrt](27/56).
(Note: From the drawing, it may seem that the enclosing rectangles for N=5 and N=6 are the same; the above table shows that it’s not the case – indeed, in the case N=6 there is a tiny spare room in the vertical direction).
Putting it all together, I get the following bounds that simultaneously satisfy all the above:
[sqrt] [7/38 * ([sqrt](45/7) + 1)] [le] a [le] 4[sqrt](3/7).
When I evaluated these bounds numerically, I’ve got a really small inteval [0.8070…, 0.8091…] – just a bit more than 0.002! The attached packings were made for the smaller endpoint.
Of course, this analysis is not complete since it doesn’t take into account the cases N>7. Simulations showed, however, that the local efficiency always stays above Jock’s threshold.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print