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?

Friday, October 05, 2018

The Least Perimeter Triangle Containing a Convex Region

Sometime back, I posted an article at arxiv on 'oriented' convex containers of convex regions: https://arxiv.org/abs/1802.10447

Among the issues mentioned there, the least area and least perimeter isosceles triangles that contain a given convex region is, as far as I know, yet to be fully resolved.

In that article, I had not touched upon the issue of finding and characterizing the smallest general triangle that just contains an input convex region. Here, 'smallest' could mean least area or least perimeter. As I found out recently, there are papers by Klee and Laskowski and by O'Rourke et al that date from 1980s which study and solve the question of least area triangle container of a given convex polygon.
However, finding the least perimeter triangle containing a given convex region is probably not yet done (to my knowledge). Here are some preliminary thoughts on this question. Note: I shall update or correct with proper date stamps (or if need arises, junk) this post as I learn more.

As given in the paper by O'Rourke and others mentioned above, the two key properties that characterize the least area triangle container (call this T) of a given convex polygonal region R are:

1. The mid point of each side of T is on R

2. At least one side of T is flush with R (ie is a side of T is a superset of a side of R).

There may be many triangles that has these properties vis-a-vis R and each is a local minimum in area of containers. One of these is the global minimum.

----------
Note inserted on October 10th 2018:
The problem of min perimeter triangle container is indeed well studied as I just learned. The first bit of major progress was made by DePano back in 1987. He proves the following basic lemma: The least perimeter containing triangle of a convex region R has at least one side flush with R. Using this lemma, efficient algorithms to find the container too were established. So most of this post are only notes to myself except perhaps, the last bit below named: "Further Questions"
----------

Consider the following figure:


ABC is a right triangle. M1, M2 and M3 are midpoints of its sides. Then a convex region (drawn in thicker lines; call this region R ) is shown inscribed in ABC with the following properties.
- An edge of R is flush with the base of ABC and contains the mid point of the base. Another edge of R is flush with the altitude of ABC and contains its mid point.
- Another edge of R, PQ is flush with the hypotenuse of ABC and contains the mid point M2 of the hypotenuse as shown. Above Q (going CCW), the boundary of R deviates inwards from the boundary of ABC.

Now, from what one understands from the above mentioned results, ABC is the least area triangular container of C.

Consider another right triangle AB'C': this has slightly less altitude than ABC and slightly more base and its hypotenuse only touches R at the end point Q of the edge of R that is flush with ABC. Obviously, AB'C' is another triangle that contains C.

Now, if ABC is chosen to have narrow base, it is seen experimentally that the newly constructed right triangle AB'C' has less perimeter and more area than ABC. So we conclude that the least perimeter triangle that contains a given convex region is not in general the same as the least area triangle container
Note: We don't say AB'C' is the least perimeter triangle container of R. We only note it is better than ABC.
------------
Now, we ask whether the least perimeter containing triangle has the above properties of the least area containing one. Consider this slightly changed figure shown below:
In this, ABC is unaltered and R has been infinitesimally changed from figure 1 so that it only touches the base and altitude of ABC at the mid points of these sides of ABC. PQ has been retained as a straight edge of R and is flush with the hypotenuse of ABC as before. Now, it looks conceivable that ABC remains the least area containing triangle of the altered R; even if there is another containing triangle with slightly less area than ABC, it appears to have more perimeter (ie is longer and thinner) than ABC. So, the same AB'C' is a lower perimeter triangular container or R than the least area container.
So, we guess that the min perimeter triangular container
- need not have mid points of its sides on the contained polygon
- need not have any side of it flush with the contained polygon.
-------
Further questions:
Which shape of R is such that its least area containing triangle and least perimeter containing triangle have greatest difference in their areas and perimeters?
More precisely, there are two questions:
- which shape of R maximizes the ratio between the area of its least perimeter triangle container and the area of its least area triangle container?
- Which shape of R maximizes the ratio between the perimeter of its least area triangle container and the perimeter of its least perimeter triangle container?
I am not quite sure if the answer to both these questions is the same shape.
The question of least perimeter quadrilateral containing R too seems not studied; the quad of least perimeter containing R may well be different from the quad of least area that contains R.
----------------------