33
$\begingroup$

This is a direct (and obvious) generalization of the recent MO question, "Covering disks with smaller disks":

How many balls of radius $\frac{1}{2}$ are needed to cover completely a ball of radius 1?

The answer may be in the paper "Covering a Ball with Smaller Equal Balls in $\mathbb{R}^n$," by Jean-Louis Verger-Gaugry, which I cannot immediately access (Springer link here). If anyone knows the answer for $\mathbb{R}^3$, I'd be curious to learn of it. And it would be especially interesting if there were a proof as satisfying as Noam Elkies's for seven half-disks covering one in $\mathbb{R}^2$. Thanks!

Update. [29May2012] A series of contributions by Will Jagy, Gerhard Paseman, Karl Fabian, and zy, have reduced the upper bound from $56$ to $33$ to $22$, with a lower bound of $16$.

Update. [5Aug2012] Ed Wynn settled the question with a careful analysis: $21$ balls are needed, and suffice!

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ A good upper bound should be derivable from a tetahedral packing: fill a ball with small metal spheres of appropriate radius r, and then replace each disjoint sphere with a sphere of radius 1/2, arranged so that the enlargment fills space. I get a rough value of about 57, which is 107 more than the -50 quoted elsewhere, but I could probably improve upon it with more care. Gerhard "Not Sure About Negative Space" Paseman, 2012.05.25 $\endgroup$
    – Gerhard Paseman
    May 26, 2012 at 4:38
  • $\begingroup$ This has a chance: one ball for each polygon of a soccer ball, then one in the center, for 33. That is, one ball centered at each vertex of the dodecahedron, one ball centered at each vertex of the dual icosahedron (i.e. the center of each pentagon of the dodecahedron), then one in the center. $\endgroup$
    – Will Jagy
    May 26, 2012 at 17:45
  • $\begingroup$ Alright,the triacontahedron idea cannot work. It is the same as one ball centered at the midpoint of each edge of an icosahedron. The trouble with that is that the edge of an icosahedron is slightly larger than the circumradius. Even at ρ=3√/2 the vertices of the icosahedron are missed. Sigh. See also contadina.com/products/paste-tomato.aspx . We are back at the soccer ball. Maybe. One value of ρ for balls matching hexagons, another ρ for pentagons. One $\rho$ to rule them all,one $\rho$ to find them, one $\rho$ to bring them all and in the darkness bind them. – Will Jagy 0 secs ago $\endgroup$
    – Will Jagy
    May 28, 2012 at 0:20
  • $\begingroup$ @Gerhard, I think I finally understand your comment. There are two methods that are guaranteed to be fairly efficient. With one, tile space with cubes, the other truncated octahedra, in either case one polyhedron inscribed in a sphere of radius 1/2. Place the unit ball in such a way as to minimize the number of polyhedra used in covering it. Then the circumscribing balls of radius 1/2 give a covering. en.wikipedia.org/wiki/Truncated_octahedron If the soccer ball thing works at all it is likely to be a little better. $\endgroup$
    – Will Jagy
    May 28, 2012 at 4:30
  • 1
    $\begingroup$ I don't know much geometry, and did not do well on the challenge geometry problems I was offered in high school. Joseph has a knack of asking accessible questions that seem to yield to ideas coming from a nongeometer, especially when enumeration is involved. Although most likely nonoriginal, my finding a reduction to covering a sphere with caps has been one of the more satisfying bits of mathematics I've done recently. Having others grind through the computations allows me to be an armchair practitioner. Gerhard "Coffee: My Idea Of Heavy-lifting" Paseman, 2012.08.05 $\endgroup$
    – Gerhard Paseman
    Aug 5, 2012 at 22:39

6 Answers 6

Reset to default
25
$\begingroup$

Here is (I'm fairly sure) an optimal solution, building on the ideas in other answers.

We know that we can generate maximum 30° caps on the sphere, by placing the half-balls at radius sqrt(3)/2. We deduce from http://neilsloane.com/coverings/index.html that we will need 20 half-balls to cover the outer surface, plus a 21st to cover the centre. So, 21 is a lower bound.

To get a 21-ball solution, scale the 20 coordinates of http://neilsloane.com/coverings/dim3/cover.3.20.txt to that radius, and add one at the origin. Note that the balls at sqrt(3)/2 give caps on the central half-ball with the same angle as the outer caps, so the cover works on the inside too.

Here are the coordinates of 21 half-balls to cover the ball: {{+0.060111,-0.479945,-0.718359},{-0.559060,+0.562759,+0.347496},{-0.164091,-0.848680,-0.053063},{-0.509173,-0.375273,-0.591535},{-0.140963,+0.208121,+0.828743},{+0.690970,+0.512659,-0.098697},{+0.377263,-0.700146,+0.342736},{-0.250648,-0.504068,+0.658097},{-0.743210,+0.007958,+0.444494},{+0.550076,+0.074555,-0.664724},{+0.521328,-0.588831,-0.362624},{+0.088527,+0.791576,+0.339956},{-0.158465,+0.221391,-0.822116},{-0.718586,-0.473046,+0.099309},{-0.339530,+0.726217,-0.327609},{+0.439846,-0.237215,+0.707294},{+0.853710,-0.140538,+0.037800},{+0.536789,+0.335659,+0.590924},{+0.243253,+0.709202,-0.433429},{-0.778146,+0.197643,-0.324694},{+0.000000,+0.000000,+0.000000}}

There is some "fat" in the surface covers (using 30° caps when 29.6..° is required), and each non-central sphere bulges convexly out of the cone that it's responsible for, so it's easy to believe that this is indeed a cover. Also I've checked it thoroughly, though I'll be grateful if someone checks it with less makeshift methods. At the positions stated, the radius of the balls can be as low as 0.49812. By moving the original coordinates further inwards, to radius 0.8595, the radius of the balls can be as low as 0.49439.

Ed Wynn, 4 August 2012.
[Graphic added by J.O'Rourke:]
         Ball Cover 21

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Congratulations, Ed, for finally settling this question! $\endgroup$
    – Joseph O'Rourke
    Aug 5, 2012 at 10:30
  • 2
    $\begingroup$ Nice topic. I am curious if Ed Wynn solution implies that a half ball (a unit ball which is centered at the origin and only contains points of non-negative $x$-coordinates) can be covered with 14 balls? 7 balls to cover the base circle of the half ball, and 7 balls to cover the rest. $\endgroup$
    – user70790
    Apr 21, 2015 at 13:37
10
$\begingroup$

Yes, the paper does cover that question, and gives bounds. However, programming the author's upper bound in mathematica reveals that in three dimensions you need at most $-50$ balls, which looks a bit suspicious. On the other hand, the author cites earlier results of Rogers, which only works for covering balls of radius at least $3/(2\log 3)\approx 1.65$ by balls of radius $1/2.$ Anyway, you can try to make sense of all this yourself.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ @Igor: Thanks for retrieving the paper for us, via your Springer superpowers! :-) $\endgroup$
    – Joseph O'Rourke
    May 26, 2012 at 1:41
  • 3
    $\begingroup$ There is a mistake in the paper on page 150. There it is stated that $(1−2/(n\log(n)))^{−n/2}<(1−2/(log(n)))^{−1}$ for al $n\geq 2$, however this is only the case when n≥7. Haven't checked the rest, but I guess the results only holds for n≥7, similarly to the results of Rogers, which has a part which only holds for n≥9, but which also restricts to covering a ball of radius at least $3/(2\log 3)$. If we correct for that mistake, we get the (true, but useless) bound 1272 for $n=3$. $\endgroup$
    – Jan Jitse Venselaar
    May 29, 2012 at 12:20
  • $\begingroup$ Perhaps the dual question has been studied? Does anyone with awesome research fu know if results have been published on (something like) r_d(m), the radius of the largest d-dimensional ball covered by m such balls of radius 1/2? Gerhard "Idle Minds: Bane Of Balls" Paseman, 2012.05.29 $\endgroup$
    – Gerhard Paseman
    May 29, 2012 at 15:47
9
$\begingroup$

Alrighty, it can be done with $56$ in an evident pattern. Take a four by four by four cube of smaller cubes, each of those of edge $1 / \sqrt 3$. Circumscribe each with a ball of diameter $1$, or radius $1/2$. These then cover the larger cube. Place the ball of diameter $2$, radius $1$, centered at the center of the large cube. It is covered by the smaller balls. Now remove the eight corner cubes. These are superfluous, the spheres circumscribing these were actually tangent to the large ball. $64 - 8 = 56$.


        [Graphic added by J.O'Rourke:]
        Ball Cover

The same method with truncated octahedra may be a little worse, maybe a little better.

Either way, it makes the soccer ball thing seem a bit unlikely. But it would be nice to see some pictures.

The third method coming from the same idea,

EDIT, Monday morning. Thanks for the figure, @Joseph. I looked up some things in SPLAG by Conway and Sloane, pages 31-34. The best (most efficient) lattice covering is traditionally called the body-centered cubic lattice, proved optimal by Bambah in 1954. The Voronoi cell is the truncated octahedron, as mentioned. Note that this polyhedron can be inscribed in a sphere, in that all vertices are the same distance from the center, true for the cube also but false for the rhombic dodecahedron. Indeed, the lattice for best covering is dual to the lattice for best sphere-packing. If we had very small radii instead of 1/2, the truncated octahedron covering would certainly win. As we have radius 1/2, hard to say. It is also uncertain whether best to put a vertex at the origin, as I did with the cubes, or the center of one of the cells, which is computationally easier, by hand anyway.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I'm willing to let 56 stand unchallenged for now. Of course, I am still thinking about Henry Segerman's problem of packing of disks of combined area 1/2 into a disk of area 1. Even with three disks of combined area 1/2 there are some interesting modifications to consider, one of which I memtion in my recent post on the MathOverflow problem. Gerhard "Nice Covering, By The Way" Paseman, 2012.05.27 $\endgroup$
    – Gerhard Paseman
    May 28, 2012 at 5:54
  • $\begingroup$ @Gerhard, Hi. The Segerman disk problem cost lots of people effort, I didn't think I had anything to add. I do not think I have any way to optimize this one either, but this way gives three fairly good answers. $\endgroup$
    – Will Jagy
    May 28, 2012 at 6:14
  • $\begingroup$ @Gerhard, 33 works, the soccer ball idea. $\endgroup$
    – Will Jagy
    May 28, 2012 at 20:23
7
$\begingroup$

Here is an idea which should generalize to dimensions 2 and greater. I will start with dimension 2.

Let us place a circle of radius 1/2 in the center of the radius 1 ball. We will place most, if not all, of the rest of the balls at a distance such that the center of the small ball is sqrt(3)/2 from the center of the large ball. This placement is chosen so that the angle of arc cut out of the two concentric circles is the same, which turns out to be 60 degrees. Now a convexity argument should show that every thing between the 60 degree arc on the small circle and the corresponding arc on the large circle will be covered by the same ball. The general covering problem is now reduced to a covering of the surface of the smaller (or the larger) sphere by circular caps which extend 60 degrees of arc

For n=2, this is a matter of taking the ratio 360/60. For n=3, I propose 6 caps around the equator, and for each hemisphere 6 more caps appropriately spaced with centers at latitude 30 degrees, and 6 more at latitude 60 degrees, sharing central longitude lines with the equatorial circles. Even if I messed up and two polar circles are needed, that gives a total of 33 spheres, but I think 31 balls suffice.

I am not familiar with higher dimensional sphere coverings, so I'll let someone else take over. I imagine that someone else can come up with a lower bound based on this style of arrangement. (Hey Noam Elkies, care to try out more dimensions?)

If Joseph understands this, maybe we will be graced with a few illustrations of it.

Edit 2012.05.31 I decided not to wait any longer for Noam Elkies. Here is my idea of a lower bound argument. It can probably be extended to open balls; I prefer to use compactness and closed balls for simplicity.

Let there be a covering of the closed unit ball by finitely many closed balls of radius 1/2. Any covering ball which contains the center, call it c, of the unit ball contains at most one point, call it p, on the boundary B of the unit ball. Since B minus p is open with respect to B, p is contained in one of the other covering balls which does not contain c. So we can assume the boundary B is covered by balls none of which contain c. The covering now has a finite number of balls which cover B plus at least one more ball covering c, and perhaps others.

Now replace the covering above with a new (perhaps identical) covering: shift each ball toward or away from c so as to maximize its intersection with B. This places each covering ball center at distance sqrt(3)/2 from c. B is still covered, and this new covering along with a ball of radius 1/2 placed with its center also at c is another (perhaps the same) covering with the same or fewer number of balls. Thus the posted problem is (essentially) the same as optimally covering B with caps of spherical radius of 30 degrees.

Elsewhere I noted Neil Sloane had a cover of a 3-d sphere with 20 caps each of radius slightly less than 30 degrees. I now claim an upper bound of 21 for the posted problem. Assuming Sloane's expertise with sphere packing, I expect 21 to be an exact bound. You can ask him for the covering number for dimensions greater than 3. END Edit 2012.05.31

Gerhard "Ask Me! About System Design" Paseman, 2012.05.27

Improve this answer
$\endgroup$
3
  • $\begingroup$ :The table of Neil Sloane(neilsloane.com/coverings) is quite interesting. It is quite amazing that highly symmetrical covering(for example,20 circle with 20 centers forming a dedocahedron) cannot do the work. Thank you for the reference $\endgroup$
    – Y. Zhao
    May 31, 2012 at 15:23
  • $\begingroup$ Thank you for doing the proper work of providing a link. I still hold hope that a 19 cap solution exists, but I will content myself with this reduction from ball covering to sphere covering. Perhaps someone can find an extension of the ideas above to handle radii other than 1/2. Gerhard "Ask Me About System Design" Paseman, 2012.05.31 $\endgroup$
    – Gerhard Paseman
    May 31, 2012 at 15:50
  • $\begingroup$ Fejes Toth gives a quite sharp bound in his book "Lagerungen in der Ebene, auf der Kugel und im Raum".He shows that if $n$ equal spherical caps covers a sphere,then radius of a cap $r_n$ is bounded by the inequality $\cos{r_n}\leq \frac{1}{\sqrt{3}}\cot{\frac{n\pi}{6(n-2)}}$.For $n=18$,$r_n$ is slightly larger than 30 degrees,so an improved lower bound is 20. $\endgroup$
    – Y. Zhao
    Jun 2, 2012 at 12:04
7
$\begingroup$

Extending the idea of W. Jagy, this is a Mathematica code visualizing that 33 spheres with radius 1/2 centered at the origin and the midpoints of the faces of a soccerball with circumradius 3/4 cover the unitsphere.

coord = PolyhedronData["TruncatedIcosahedron", "VertexCoordinates"]; faces = PolyhedronData["TruncatedIcosahedron", "FaceIndices"]; f6 = Select[faces, Length[#] == 6 &]; f5 = Select[faces, Length[#] == 5 &]; len = Norm[coord[[1]]] // Simplify; Graphics3D[{{Opacity[0.3], Sphere[{0, 0, 0}, len*4/3], Sphere[ Mean[coord[[#]]], len*2/3] & /@ f6, Sphere[ Mean[coord[[#]]], len*2/3] & /@ f5, Opacity[1], Sphere[{0, 0, 0}, len*2/3]}, {Opacity[0.4], PolyhedronData["TruncatedIcosahedron" , "Faces"]}}, Boxed -> False]
        [Graphic from the above code added by J.O'Rourke:]
        Cover

Plotting only three outer spheres as in

Graphics3D[{{Opacity[0.3], Sphere[{0, 0, 0}, len*4/3], Sphere[ Mean[coord[[#]]], len*2/3] & /@ Take[f6, 2], Sphere[ Mean[coord[[#]]], len*2/3] & /@ Take[f5, 1], Opacity[1], Sphere[{0, 0, 0}, len*2/3]}, {Opacity[0.4], PolyhedronData["TruncatedIcosahedron" , "Faces"]}}, Boxed -> False]
        [Graphic from the above code added by J.O'Rourke:]
        Three Spheres

shows that the two intersection points of three neighboring outer spheres lie either outside the sphere with radius 1 or inside the sphere of radius 1/2. This can easily be made rigorous by calculation:

mcl = Chop[ Join[Mean[coord[[#]]] & /@ Take[f6, 2], Mean[coord[[#]]] & /@ Take[f5, 1]]]; erg = Solve[(Norm[{x, y, z} - #] == len*2/3) & /@ mcl, {x, y, z}] // N; ((Norm[{x, y, z}]/len*3/4) /. #) & /@ erg

that yields the distances

{0.216794, 1.06042}

Improve this answer
$\endgroup$
2
  • $\begingroup$ I see, centers at $\rho = 3/4,$ which is indeed much less than $\sqrt 3 / 2 \approx 0.866.$ If the result does cover the sphere $\rho = 1,$ then it definitely also covers the sphere $\rho = 1/2,$ so a single extra central sphere does suffice. Therefore just two cases, is each pentagon on $\rho = 1$ covered by its 1/2 ball, and is each hexagon covered. The figure 3/4 is what makes it all understandable. $\endgroup$
    – Will Jagy
    May 28, 2012 at 18:51
  • $\begingroup$ (@Karl: I had some difficulty avoiding interference between "[1]" in your code and the image-inclusion markup "[1]". Apologies if I altered anything.) $\endgroup$
    – Joseph O'Rourke
    May 28, 2012 at 19:16
7
$\begingroup$

This is a numerical calculation of an improved covering like the one proposed by Gerhard Paseman. It gives the following list of 22 centers for 1/2-balls that cover the unit ball. All, besides the central one, are on the sphere with radius Sqrt[3]/2.

2 are on the poles

6 on the upper hemisphere at latitude t = 0.20483559485813116` Pi

6 on the lower hemisphere at latitude t = 0.20483559485813116` Pi

7 lie distributed over the equator with angular distance 2/7.15 Pi, and phase shift 0.86 wrt the six upper and lower.

I didn't yet calculate all intersections of neighboring balls explicitely.

Centers: {{0, 0, 0}, {0.570962, 0.651155, 0.}, {-0.137028, 0.855116, 0.}, {-0.745836, 0.440145, 0.}, {-0.81481, -0.293402, 0.}, {-0.294026, -0.814585, 0.}, {0.439574, -0.746173, 0.}, {0.855011, -0.137682, 0.}, {0.599996, 0.346408, 0.519621}, {0., 0.692816, 0.519621}, {-0.599996, 0.346408, 0.519621}, {-0.599996, -0.346408, 0.519621}, {0., -0.692816, 0.519621}, {0.599996, -0.346408, 0.519621}, {0.599996, 0.346408, -0.519621}, {0., 0.692816, -0.519621}, {-0.599996, 0.346408, -0.519621}, {-0.599996, -0.346408, -0.519621}, {0., -0.692816, -0.519621}, {0.599996, -0.346408, -0.519621}, {0., 0., 0.866025}, {0., 0., -0.866025}}

Graphics:

ddp = 0.86; equator = Take[Table[{Cos[p], Sin[p], 0}, {p, ddp, 2 Pi, 2/7.15 Pi}], 7]; t = 0.20483559485813116 Pi; dp = 0; up = Table[{Cos[p] Cos[t], Sin[p] Cos[t], Sin[t]}, {p, Pi/6 + dp, 11/6 Pi + dp, Pi/3}]; dn = Table[{Cos[p] Cos[t], Sin[p] Cos[t], -Sin[t]}, {p, Pi/6 + dp, 11/6 Pi + dp, Pi/3}]; poles = {{0, 0, 1}, {0, 0, -1}}; out = Sqrt[3]/2 Join[equator, up, dn, poles]; Graphics3D[{{Opacity[1], Red, Sphere[{0, 0, 0}, 1/2]}, {Opacity[0.4], Red, Sphere[{0, 0, 0}, 1]}, {Opacity[0.2], Sphere[ #, 1/2] & /@ out}}, Boxed -> True]


        [Graphic from the above code added by J.O'Rourke:]
        Cover by 22 Balls

KF-PS: I changed the phase shift from 0.85... to ddp = 0.86. In this case numerical calculation shows that in fact the minimum of the maximum intersection points of three neighboring spheres is >1, which implies that the unit ball is covered.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Interesting. Have you tried 2 or 3 circle polar covers, and then extended the patttern down? Also, can you calculate the area of the spherical cap so as to get a rough lower bound? Finally, can you visualize and then communicate results for n=4? Gerhard "Just Asking For The World" Paseman, 2012.05.28 $\endgroup$
    – Gerhard Paseman
    May 29, 2012 at 4:13
  • 1
    $\begingroup$ The area of spherical cap contained in a radius-1/2 ball is $2\pi (1-\sqrt{3}/2)$.We need $4/(2-\sqrt{3})\approx 14.8$ balls to cover the surface of radius-1 ball,1 ball to cover the center,so a rough lower bound might be 16 $\endgroup$
    – Y. Zhao
    May 29, 2012 at 14:26
  • $\begingroup$ If we consider that consider that near the intersection of (two delta neighborhoods of) circle boundaries any epsilon neighborhood of a point must be covered by a third circle boundary, we might shave the cap area enough to get a lower bound of 17 or even 18. I certainly do not see at present how to get a covering with fewer than 20 balls. Gerhard "Ask Me About System Design" Paseman, 2012.05.29 $\endgroup$
    – Gerhard Paseman
    May 29, 2012 at 16:43
  • 1
    $\begingroup$ I crudely estimated the necessarry overlap from a planar honeycomb and found that with this overlap one needs more than 21 spheres to cover the unit sphere, so the 21 above are better than that, such that each sphere on average cuts more than 6 others at its periphery. $\endgroup$
    – Karl Fabian
    May 29, 2012 at 16:50
  • $\begingroup$ Karl, I think we should try for 19. Have each pole lie on the boundary of 3 symmetrically placed caps, and add 3 more caps to create a (when stereographically projected) triangle of 6 circles. This configuration already crosses the equator, and I hope a judiciously placed belt (this is your part) of 8 or 7 or even (dare I hope?) 6 circles will finish the cover. I sit here with a smartphone and paper and pen; perhaps you can supply the mathematics and computation? Gerhard "Oh, And Some Imagination, Too" Paseman, 2012.05.29 $\endgroup$
    – Gerhard Paseman
    May 29, 2012 at 19:54

Your Answer

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

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