TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Saturday, October 27, 2018

Variants of the Kissing Number Problem

Let me record two variants of the famous kissing number problem that has a history going back at least to a debate between Newton and Gregory. I don't know if these questions have been explored.
Note: On this page are a proof that the kissing number of squares is 8 and an informed guess that the kissing number for unit cubes is 26 (no full proof of latter statement):
https://mathoverflow.net/questions/117579/the-kissing-number-of-a-square-cube-hypercube

1. CORDONING:
Arrange the least number of unit spheres touching a central unit sphere (call this unit sphere S) such that no more unit spheres can touch S. In 3D, the answer appears to be 4 unit spheres with their centers at the vertices of a regular tetrahedron and all touching S. What about higher dimensions?

------------
Note inserted on October 28th, 2018: This problem is the same as 'blocking'. It was first attacked at least 20 years ago and features in 'Research Problems in Discrete Geometry by Moser, Brass and Pach. Just that I couldn't find the right search key. So, what follows here on cordoning are notes to myself
------------

Remark: The question can easily go over to other convex shapes (cubes, tetrahedra,...) and dimensions.

In 2D, a unit circle can be cordoned by 4 unit circles; and a unit square can be cordoned by a minimum of 4 squares thus:


A 3D unit cube can be cordoned by 8 cubes. Indeed, view above cordoning layout of squares as a layout of cubes all lying on the XY plane and viewed from +Z with the central cube centered on Z axis. Shift the 4 surrounding cubes half unit in +Z direction. Then add another layer of surrounding cubes directly below the quartet shifted upwards. Now, the central cube can be touched only by a unit cube approaching it vertically from above or from below - all other directions of approach are blocked. And these two remaining directions can also be blocked by tilting the cubes already placed in the two layers slightly towards the Z axis by rotating them about the edges of the central cube they are touching. Of course, there may be better cordoning schemes and I don't know them.

2. SCREENING
If the central unit sphere S is a source of light, arrange a least number of opaque and perfectly absorbing unit spheres around it such that no light is visible from any far off point.

------------
Note inserted on October 28th, 2018: This problem too is fairly well explored by experts. So, only the last bit of this post, 'further questions' might have (if at all) something of interest to experts.
------------

As before, the question can easily go over to other convex regions (cubes, tetrahedra,....) and to dimensions other than 3. In 2D, although the kissing number of a unit square is obviously 8, we see that five unit squares are enough to screen a unit square:


Note: For circles, the kissing number is 6 as is the screening number - this looks obvious.

In 3D, the kissing number of spheres is, very famously, 12 but I don't know if the best way to screen is to form a possible best kissing arrangement and plug the gaps with more spheres.

On the best way to screen a unit cube:
One can build on top of the screening configuration for squares shown above and achieve a screening of a unit cube with 13 unit cubes. Indeed, think of the screening squares as a view from above of an arrangement of 5 cubes around the central yellow one with all cubes resting on the XY plane. Now, the yellow cube can be seen only from above or below. See picture below.

Now, an additional layer formed by 4 cubes could be put above (dotted squares in picture above) and another such layer below to totally screen the yellow cube; so we have a screening with 5+4+4 = 13 cubes.
But I have no proof of optimality for this screening arrangement. Looks like one can do better.
Note: If one goes to non-convex objects, one can have shapes screenable by 3 copies of themselves, at least in 2D.
--------------
Further Questions:
Note that these questions can be stated in any dimension.
1. Is the sphere (or maybe ellipsoids below some critical eccentricity) the worst 3D region for screening - ie it needs most opaque copies to screen? Which convex shape has the least screening number?
2. Likewise, is the sphere the best shape for cordoning - ie it needs least copies to cordon (maybe there are equally good shapes but none that is better)? And which convex shape needs max copies to cordon?
3. It appears that the units used for the best screening need not all touch the central unit. While building the best cordoning around any given central convex shape, do the cordoning units all necessarily touch the central unit?

4. One also thought of both these questions with the following additional constraint: the copies of the central body (call this S) to be put around S all need to be identical up to translations (iow the 'blocking copies' should all have same orientations).
For the questions thus constrained, will the optimal answers to both (least number of blocking copies) be necessarily achieved when the common orientation of the blocking copies is identical to the orientation of central copy S ( ie no other common orientation of blocking copies can beat it)? If so, does this property hold in all dimensions?

0 Comments:

Post a Comment

<< Home