Consider two touching unit balls which will be called central balls. What is the maximum number $k$ of non-overlapping unit balls so that each ball touches as least one of two central balls?
An easy lower bound $k\geq 18$ is achieved by the face-centered cubic lattice. I conjecture that $k=18$.
$\begingroup$
$\endgroup$
6
-
$\begingroup$ You might investigate packing which involve 10 spheres in two rings of five around the contact point of the central spheres. (Note there are several ways, but probably fewer than 20, to bunch them up on the different rings.) You might be able to place another 9 spheres with a nonsymmetric arrangement on the two rings. $\endgroup$– The Masked AvengerCommented Jun 10, 2015 at 19:00
-
$\begingroup$ Actually, if you can push the two rings of five close enough together, you may be able to get two more rings of five on the outside. $\endgroup$– The Masked AvengerCommented Jun 10, 2015 at 19:07
-
$\begingroup$ What leads you to your conjecture? $\endgroup$– Moritz FirschingCommented Jun 10, 2015 at 19:31
-
1$\begingroup$ Frisching: I was looking for a more rigid version of the kissing problem in 3 dimension. Fejes-Toth's conjecture (now proven by Hales) states that infinite kissing configurations are laminates, i.e. unions of hexagonal layers. On the other hand, the classical kissing problem is very degenerate. If you want to know my motivation you can read my paper with Flatley. $\endgroup$– Florian TheilCommented Jun 12, 2015 at 14:54
-
$\begingroup$ Avenger: We were unable to fit 19 balls with simulated annealing on a computer. If you can give me the coordinates of a promising starting configuration I am happy to give another go. $\endgroup$– Florian TheilCommented Jun 12, 2015 at 14:59
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
2
Using global nonlinear optimization one can obtain a configuration of $19$ spheres, that touch at least one of the central unit spheres and have almost no overlap. In fact, if one takes their radii to be $.99$ instead of $1$ they are non-overlapping.
Below are the coordinates; the two central spheres have radius $1$ and are centered around the origin and $(2,0,0)$. Here is a picture of the configuration:
Maybe this is helpful as a starting point in the simulated annealing approach you mentioned in the comments, but I am not so sure, since it seems to be somewhat jammed already.
(1.30155675907051, 1.87408031823623, 0.000000000000000),
(3.30307693251716, -1.48756032724292, 0.298587978254738),
(3.77087392448039, -0.00565125397965555, -0.929501805767173),
(2.34028624585583, 1.21452857880052, -1.55213581949477),
(1.49324421375722, -1.89375136244257, -0.396111537780328),
(3.31658479709791, 0.0846873881998760, 1.50314088439273),
(1.46434039083497, 0.727511022954233, 1.78431961671711),
(1.82006459231285, -1.21042374283863, 1.58192844712867),
(2.17723615440802, -0.736686335972064, -1.85091344691338),
(3.24812939881743, 1.55286888817322, 0.175417273814499),
(-0.234051719598306, 1.57207701538230, 1.21399903223316),
(-0.182142247556194, -1.45688908753032, -1.35804947932633),
(-1.35706161319061, 0.134224681025498, -1.46299949180272),
(-1.82011109002214, 0.745105549605677, 0.363336400498419),
(0.560694305152308, 0.407540066521993, -1.87604184131108),
(-0.536544075078242, 1.78215924389985, -0.732139935326408),
(-1.60854779879003, -1.18847287273622, -0.0103058129362229),
(-0.850339283181967, -0.217696133065399, 1.79708972984823),
(0.0325533674370459, -1.76736000103794, 0.935616858014407)]
answered Jun 12, 2015 at 18:16
-
$\begingroup$ I looked with Matlab for a counter-example starting with your initial guess. I could not find one. Your example shows that a potential proof of the conjecture cannot be simple as there are many almost admissible 19 sphere configurations. $\endgroup$ Commented Jun 25, 2015 at 10:55
-
$\begingroup$ So if you fix the radius of the two central spheres and ask for the largest radius $r$, such that one can pack 19 spheres you get an lower bound bound of $\approx0.9912$. (In the coordinates above the centers of the spheres are distance $1$, not $r$ from the central spheres, hence the slightly smaller radius.) From global optimization, one also gets an upper bound on the radius: something like $2$ is achieved easily: it is therefore not possible to pack 19 spheres with radius $2$. You want to decrease the the bound below $1$. I conjecture the maximal radius is indeed very close to $0.991$. $\endgroup$ Commented Jun 26, 2015 at 20:19
$\begingroup$
$\endgroup$
This problem might be small enough to be solvable by a global optimization algorithm such as SobolOpt or VNS. See New Formulations for the Kissing Number Problem for more information about this approach.
answered Jun 10, 2015 at 20:17