8
$\begingroup$

Packing problems are well known, often hard and sometimes fun. If we want to pack unit squares into a circle then this beautiful page shows some solutions. One interesting feature is shown first in the 6 square case where the best known solution does not involve all the squares being aligned with each other.

If we aim to find the smallest radius sphere to pack n unit cubes instead, what is the smallest n for which it is better to have non aligned cubes? By aligned I mean the sides are aligned with the x, y, z axes

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ The 3 case is not aligned too. $\endgroup$
    – Weather Vane
    Commented Aug 27 at 10:38
  • 1
    $\begingroup$ @WeatherVane I meant axis aligned . $\endgroup$
    – Simd
    Commented Aug 27 at 11:40
  • 1
    $\begingroup$ Is there some clever elegant solution to this? Even in the planar case it seems starting at n=8 this looks like some numeric wiggling. $\endgroup$
    – quarague
    Commented Aug 27 at 13:32
  • $\begingroup$ @quarague it's hard to get the optimal answer in general but my question doesn't quite call for that. $\endgroup$
    – Simd
    Commented Aug 27 at 17:21
  • 1
    $\begingroup$ @WeatherVane lucky there are 1000s here :) $\endgroup$
    – Simd
    Commented Aug 27 at 20:51

2 Answers 2

Reset to default
7
+50
$\begingroup$

Some empirical evidence that n=6

The best axis-aligned configuration I found uses a radius of $1.630998544...$.

Here's configuration with $6$ cubes that fits in a sphere with radius ~$1.627$. (The corners that touch the sphere are circled in red).

enter image description here

View from "above":
enter image description here

How

I wrote an app that uses a physics simulator. $6$ cubes are simulated, and any cube corner that leaves a user-defined "repel radius" is pushed towards the origin (with a force proportional to how far it trespassed the "repel radius").

Cubes would nearly always quickly get stuck in a local minimum, but "jiggling" all the cubes (applying a random force to each during every simulation step) worked nicely to reach a better minimum.

This process revealed a handful of promising arrangements, and let me find the approximate radius for ideal version of each.

Here's a long, boring, rambly video of the app: https://youtu.be/931f3PkUfzg

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ What an amazing simulator! One dumb question, your solution for 5 didn't seem axis aligned either. Was it no better than an axis aligned solution? $\endgroup$
    – Simd
    Commented Sep 5 at 11:06
  • 1
    $\begingroup$ Nice! You get 1.63063 with the approximate radius values with 3 places, but using the exact expressions (for example √2 instead of 1.414 etc) then the sphere radius is 1.630998544. $\endgroup$
    – Weather Vane
    Commented Sep 5 at 12:06
  • 2
    $\begingroup$ @Simd - thanks! The solution for 5 has two layers (of 4 cubes and 1 cube). Each layer is free to rotate independently of the other layers. Think of N=2, and how the two cubes are free to rotate. Weather Vane - thanks, I updated this answer to use your value. $\endgroup$
    – Tom Sirgedas
    Commented Sep 5 at 13:42
  • 1
    $\begingroup$ I'm happy to have verified the radius 1.627097 by permuting the three variables (angle, x-offset, z-offset) by progessively smaller steps. $\endgroup$
    – Weather Vane
    Commented Sep 6 at 10:17
  • $\begingroup$ Thanks @Weather Vane! $\endgroup$
    – Tom Sirgedas
    Commented Sep 6 at 15:25
8
$\begingroup$

(partial answer)

Simplification

Let's start with an intuitive simplification. The cubes must be stacked in independent "layers", where each layer "sits" on $y=k$ for some integer $k$.

Now, given a sphere with a certain radius and offset, notice that the cubes in each layer must fit inside a cylinder.

Example

enter image description here
There are 3 cylinder-shaped layers here: red, yellow, and blue. The y-axis passes through the center of each cylinder.

In this example, the layers have radii $1.118$, $1.688$, and $0.80564$. According to this page, these layers can contain $2$, $6$, and $1$ cubes respectively. So, this sphere contains $9$ cubes in total. This happens to be optimal given the "layers" constraint. (It might be possible to show that no axis-aligned cube configuration can fit $9$ cubes in a sphere of radius $1.7915$). Note that the middle layer in this example contains a non-axis-aligned cube.

Per-layer view

For convenience, here's what each layer looks like (not to scale): enter image description here

Optimal radii (under "layers" constraint)

Here's a table of optimal radii for packing cubes in a sphere, with the "layers" constraint. The numbers in curly braces indicate the per-layer cube count. Note that the radius/y-offset values are only accurate to about 3 or 4 digits, since the reference page provides similarly low-precision values.

  1:                 {1} r = 0.865938 y-offset =      0.5
  2:               {1,1} r =  1.22468 y-offset =        0
  3:                 {3} r =  1.38165 y-offset =      0.5
  4:               {1,3} r =  1.47084 y-offset = 0.289774
  5:               {1,4} r =  1.54602 y-offset = 0.374887
  6:               {3,3} r =  1.63063 y-offset =        0
  7:             {1,5,1} r =  1.65827 y-offset =      0.5
  8:               {4,4} r =  1.73188 y-offset =        0
  9:             {1,6,2} r =  1.79151 y-offset = 0.600145
 10:             {1,6,3} r =  1.83486 y-offset = 0.693183
 11:             {2,7,2} r =  1.87081 y-offset =      0.5
 12:             {2,7,3} r =   1.9259 y-offset =  0.56817
 13:             {2,7,4} r =  1.97237 y-offset = 0.624912
 14:             {1,7,6} r =  2.01939 y-offset = 0.891583
 15:             {4,8,3} r =  2.04565 y-offset = 0.478272
 16:             {4,8,4} r =  2.06141 y-offset =      0.5
 17:             {4,8,5} r =  2.12283 y-offset = 0.583361
 18:             {5,9,4} r =  2.14767 y-offset = 0.453592
 19:             {6,9,4} r =  2.17157 y-offset = 0.366146
 20:            {5,10,5} r =  2.17935 y-offset =      0.5
 21:            {5,10,6} r =  2.21988 y-offset = 0.558297
 22:            {6,10,6} r =  2.25817 y-offset =      0.5
 23:            {6,11,6} r =  2.26976 y-offset =      0.5
 24:            {6,12,6} r =  2.29122 y-offset =      0.5
 25:            {7,12,6} r =  2.30552 y-offset = 0.438123
 26:            {7,12,7} r =  2.34461 y-offset =      0.5
 27:         {2,10,11,4} r =  2.38964 y-offset = 0.100789
 28:         {2,10,12,4} r =  2.40112 y-offset = 0.124962
 29:         {3,10,12,4} r =   2.4268 y-offset = 0.056792
 30:         {3,11,12,4} r =  2.43954 y-offset = 0.024475
 31:         {4,12,11,4} r =  2.44941 y-offset =  0.99995
 32:         {4,12,12,4} r =  2.44943 y-offset =        1
 33:         {4,12,12,5} r =  2.50068 y-offset = 0.0625206
 34:         {3,12,13,6} r =  2.51134 y-offset = 0.143302
 35:         {4,12,13,6} r =  2.53686 y-offset = 0.106243
 36:         {5,13,13,5} r =  2.56377 y-offset =        1
 37:         {5,13,13,6} r =  2.58387 y-offset = 0.0437229
 38:         {6,13,13,6} r =  2.61713 y-offset =        1
 39:         {4,12,15,8} r =  2.64823 y-offset = 0.239136
 40:         {4,13,15,8} r =  2.65881 y-offset = 0.223263
 41:      {2,12,16,10,1} r =  2.68245 y-offset = 0.438368
 42:      {1,12,16,12,1} r =  2.69253 y-offset =      0.5
 43:      {2,12,16,12,1} r =  2.71008 y-offset = 0.468722
 44:         {7,15,15,7} r =  2.72325 y-offset =        0
 45:      {2,12,17,12,2} r =   2.7386 y-offset =      0.5
 46:      {1,12,17,13,3} r =  2.74689 y-offset = 0.595535
 47:      {4,13,17,12,1} r =  2.76409 y-offset = 0.375037
 48:      {3,13,18,12,2} r =   2.7907 y-offset =  0.47569
 49:      {3,13,18,13,2} r =  2.80273 y-offset = 0.489245
 50:      {3,13,18,13,3} r =  2.81228 y-offset =      0.5
 51:      {1,12,17,15,6} r =  2.83083 y-offset = 0.736065
 52:      {6,15,18,12,1} r =  2.83545 y-offset = 0.274248
 53:      {1,12,18,15,7} r =  2.86339 y-offset = 0.774735
 54:      {5,15,19,13,2} r =  2.87775 y-offset =  0.36579
 55:      {2,13,19,15,6} r =  2.88566 y-offset = 0.659555
 56:      {4,13,19,15,5} r =  2.91763 y-offset = 0.552087
 57:      {2,13,19,16,7} r =   2.9258 y-offset = 0.703776
 58:      {5,15,20,14,4} r =  2.93966 y-offset = 0.478315
 59:      {5,15,20,15,4} r =  2.94915 y-offset = 0.489566
 60:      {4,15,21,15,5} r =  2.95764 y-offset = 0.500389
 61:      {5,15,21,15,5} r =  2.95797 y-offset =      0.5
 62:      {7,16,21,14,4} r =  2.98152 y-offset =  0.37535
 63:      {7,16,21,15,4} r =  2.99809 y-offset = 0.396111
 64:      {4,15,21,17,7} r =  3.00946 y-offset =  0.62504
 65:      {6,16,21,16,6} r =  3.02161 y-offset =      0.5
 66:      {8,18,21,15,4} r =  3.04339 y-offset = 0.312951
 67:      {7,17,21,16,6} r =  3.04957 y-offset = 0.460214
 68:      {6,17,21,17,7} r =  3.07356 y-offset = 0.510109
 69:      {7,17,22,17,6} r =  3.07771 y-offset = 0.495015
 70:      {7,17,22,17,7} r =  3.08175 y-offset =      0.5
 71:      {7,17,22,18,7} r =  3.10877 y-offset = 0.533235
 72:      {7,18,23,17,7} r =  3.11626 y-offset = 0.482562
 73:      {7,18,23,18,7} r =  3.12459 y-offset =      0.5
 74:      {9,19,23,17,6} r =  3.14122 y-offset =  0.35655
 75:      {8,19,23,18,7} r =  3.15434 y-offset = 0.438972
 76:      {8,19,24,18,7} r =  3.15857 y-offset = 0.448213
 77:     {5,16,23,21,12} r =  3.17209 y-offset = 0.750014
 78:     {10,19,24,18,7} r =  3.18557 y-offset = 0.376805
 79:     {11,21,24,17,6} r =  3.18931 y-offset = 0.294015
 80:     {6,17,24,21,12} r =  3.19699 y-offset = 0.715035
 81:     {7,18,24,21,11} r =  3.21743 y-offset = 0.665459
 82:     {7,18,24,21,12} r =  3.22555 y-offset = 0.675249
 83:     {12,21,25,18,7} r =  3.24149 y-offset = 0.346821
 84:     {10,21,26,19,8} r =  3.25008 y-offset = 0.437294
 85:     {12,21,26,19,7} r =  3.26155 y-offset = 0.374451
 86:     {9,20,26,21,10} r =  3.26861 y-offset = 0.521296
 87:     {10,21,26,21,9} r =  3.27838 y-offset = 0.499823
 88:    {10,21,26,21,10} r =  3.27851 y-offset =      0.5
 89:    {10,21,27,21,10} r =  3.29911 y-offset =      0.5
 90:     {12,21,27,21,9} r =  3.30889 y-offset = 0.439071
 91:    {10,21,27,21,12} r =  3.31688 y-offset = 0.550105
 92:   {4,17,25,25,17,4} r =  3.34161 y-offset =        0
 93:   {4,17,25,26,17,4} r =  3.34961 y-offset = 0.0133453
 94:   {4,17,26,26,17,4} r =  3.35357 y-offset =        0
 95:   {5,17,26,26,17,4} r =  3.36314 y-offset = 0.968355
 96:   {4,17,26,26,18,5} r =  3.36773 y-offset = 0.043344
 97:   {6,18,26,26,17,4} r =  3.38293 y-offset = 0.931698
 98:   {4,17,26,27,18,6} r =  3.38884 y-offset = 0.0779653
 99:   {4,17,26,27,19,6} r =  3.39633 y-offset = 0.0879853
100:   {7,19,27,26,17,4} r =  3.41088 y-offset = 0.896016
101:   {5,18,27,27,18,6} r =  3.41887 y-offset = 0.0269029
102:   {6,19,27,27,18,5} r =  3.42474 y-offset = 0.962031
103:   {6,19,27,27,18,6} r =  3.44489 y-offset =  0.99701
104:   {6,19,27,27,19,6} r =  3.44663 y-offset =        0
105:   {4,17,27,28,21,8} r =  3.46141 y-offset = 0.159424
106:   {8,21,28,27,18,4} r =  3.47742 y-offset =  0.86006
107:   {7,20,28,27,19,6} r =  3.48771 y-offset = 0.947989
108:   {7,21,28,27,19,6} r =   3.4989 y-offset = 0.935212
109:   {6,19,28,28,21,7} r =  3.50764 y-offset = 0.0490244
110:   {7,20,28,28,20,7} r =  3.51702 y-offset =        0
111:  {3,17,27,29,23,12} r =  3.52237 y-offset = 0.278439
112:   {7,21,28,28,21,7} r =  3.53514 y-offset =        0
113:  {12,23,29,27,18,4} r =  3.54536 y-offset = 0.751339
114:   {7,21,29,29,21,7} r =  3.55552 y-offset =        0
115:  {4,18,27,30,24,12} r =    3.561 y-offset = 0.268229
116:  {12,24,30,28,18,4} r =  3.57109 y-offset = 0.755163
117:  {12,23,30,28,19,5} r =  3.57674 y-offset = 0.791655
118:  {12,24,30,28,19,5} r =  3.58473 y-offset = 0.782746
119:  {7,21,29,30,22,10} r =  3.59734 y-offset =    0.108
120:  {7,21,29,30,23,10} r =  3.60337 y-offset = 0.118263
121:  {12,24,30,29,20,6} r =  3.61222 y-offset = 0.836975
122:  {12,24,30,29,21,6} r =  3.62226 y-offset = 0.849753
123:  {12,24,30,29,21,7} r =  3.62557 y-offset = 0.853959
124:  {12,24,31,29,21,7} r =  3.63433 y-offset = 0.843872

This table was computed by forcing the sphere to pass through $(x_0,y_0)$ and $(x_1,y_1)$ for $x_0$ and $x_1$ being members of the set of radii from the reference page, and $y_0 = 0$ and integer $y_1$.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Yes, and for orthogonal layers (3,5,1) I get r=1.8349, and (3,4,2) gives r=1.9259. $\endgroup$
    – Weather Vane
    Commented Aug 29 at 13:13
  • $\begingroup$ Which of the cubes are touching the sphere in this packing? $\endgroup$
    – Simd
    Commented Aug 29 at 18:58
  • 1
    $\begingroup$ In the red layer, both cubes have two of their top corners touching the sphere. In the yellow layer, five of the cubes have a bottom corner touching the sphere (though two of these cubes can be moved upwards a bit, in which case they'll stop touching the sphere). In the blue layer, the cube is not touching the sphere. $\endgroup$
    – Tom Sirgedas
    Commented Aug 29 at 19:45
  • $\begingroup$ ...which explains why the available radius of the blue layer is more than the needed 0.70711 and variously given as 0.80564 and 0.80654. $\endgroup$
    – Weather Vane
    Commented Aug 29 at 19:59
  • 1
    $\begingroup$ FWIW I worked out a more precise value for Friedman's $R_6 = 1.688542968$ giving me a slightly larger $1.791877315$ for the sphere radius. But slices (2 6 1) still beats any other other permutation of slices. I don't have an exact expression, although the others used do – my $R_6$ value was obtained by sliding blocks in ever smaller steps until six points touch the circumference. There is a gap between the angled square and the 'central' square. $\endgroup$
    – Weather Vane
    Commented Sep 4 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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