TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Saturday, January 19, 2019

A bit more on Kissing Numbers and Spheres

PART 1

The kissing number of spheres in 3D is 12 as is well known; in 2D the kissing number of disks is 6.

Question: Can a unit sphere be kissed by 12 spheres which are all mutually equal but with radius slightly greater than 1? The reason for asking this is that there is quite a bit of room left after 12 unit spheres kiss the central unit sphere; this left over space has been proved to be not enough to squeeze in a 13th unit kissing sphere but what prevents the 12 kissing spheres from being slightly bigger?

If the answer to above question is "Yes", then how much bigger can the 12 kissers be? Further in that case, can one have an infinite (in all 3D directions) arrangement of spheres such that every one of them has a unique and finite radius and every one of them is touched by exactly 12 other spheres?

Note: In 2D, we cannot form an infinite (in every direction in 2D) arrangement of mutually non-identical and finite disks with every sphere being touched by 6 other disks. Indeed, there has to be a finite smallest disk; it cannot be kissed by 6 disks all of which are strictly larger.

And as usual, what about 4D?

-----

Note: The face centered cubic and hexagonal close packed structures both have a packing factor of 0.74, consist of closely packed planes of atoms (ie in each plane every sphere has 6 others touching it), and have a coordination number of 12. The difference between the fcc and hcp is the stacking sequence. The hcp layers cycle among the two equivalent shifted positions whereas the fcc layers cycle between three positions. So, obviously, in 3D, any arrangement of slightly bigger but mutually identical 12 spheres kissing a central unit sphere cannot be either hcp or fcc. But there may well be other options.

-----

PART 2

Another direction to extend the question:
In an arrangement of copies of a certain region C, let us define the neighborhood of any single unit, C0 as the set of copies of itself kissing C0 plus the relative positions and orientations of these kissing copies. Let residents of two unit C's in the arrangement, C1 and C2, note their respective neighborhoods. If these neighborhoods are different for such every pair {C1, C2}, we say every unit C in the arrangment has a unique neighborhood.

Question: Given any 2D convex shape C, fill the plane with a rigid arrangement (there could be gaps among units) of identical copies of C such that each unit sees a 'unique neighborhood'. No constraint on the number of neighbors each unit has. C could be a disk or square or... This question goes naturally to 3D.

A constrained version: Form infinite (in all directions)and connected - maybe with rigidity relaxed - layouts of copies of C such that every unit C touches a specified number n of other units and has a 'unique neighborhood'

Special cases: One can try to form a connected and infinite arrangement of disks on a plane such that every disk touches exactly 4 (or 5 or even 3) other disks and has a unique neighborhood. In the 3-disk case, one has an equivalent problem of tiling the plane with hexagons all with all sides of equal length and at every vertex, the 3 angles meeting being a unique set.

Guess: Insisting on rigidity and fixing the number of neighbors might make such 'locally unique' layouts hard to achieve especially for disks where each unit is fully specified by its position alone (no scope for changing orientation).

Note: In the '4 disks touching each disk' case, there is the similar but perhaps not quite equivalent problem of forming a rigid and plane-filling arrangement of rhombuses with all the sides equal to 1 but with the 4 angles meeting at a vertex unique. In both cases, the angles are constrained to be at least 60 degrees and also have an upper bound.

And here is something more basic that I don't know as of now: When arranging identical disks to fill the plane and such that each disk touches exactly n other disks, there is only one arrangement possible when n =6. However if n =3, 4 or 5, will the possible arrangements be infinitely many?

Update (June 2019): Some of the issues raised in this post got resolved in a future post: https://nandacumar.blogspot.com/2019/03/more-on-2d-layouts-with-unique.html

Sunday, January 06, 2019

Wrapping Convex Bodies with Paper

This post has been updated on 27th November 2019

Recording some questions on optimally wrapping any given convex 3d body with a suitable single sheet of paper. This post is a prelude to further searches. First, a quote from a paper by Erik Demaine et al:

We consider three objectives in such wrappings: minimizing area of wrapper, minimizing perimeter, and the shape tiling the plane. Minimizing area naturally minimizes the material usage. Minimizing perimeter results in a minimum amount of cutting from a sheet of material....
Minimization of both area and perimeter (of the wrapper)... is a bicriterion optimization problem. Just minimizing the area is not interesting: starting from an arbitrarily thin rectangular strip, it is possible to wrap any surface using material arbitrarily close to the surface area.... However, Minimizing perimeter alone remains an interesting open problem.


With reference to the above, one feels that minimizing the area of the wrapper alone can become interesting if the paper is also constrained NOT to wind multiple times around the body being wrapped - this concept of 'winding' can be made precise, it seems. In what follows "least area" means "least area without multiple winding"

Another constraint that can be applied: the wrapping sheet ought to be a convex region. The least perimeter wrapping sheet for any convex 3d region is naturally convex. But is there any convex 3D region at all for which the least area wrapping sheet is convex? Seems the answer is NO.

I am not sure about the convex wrapper of least area and least perimeter for even a cube. To find a convex wrapper of any polyhedron, one can find a *net* of the polyhedron and take its convex hull. As given here , one can do better for a cube than to take a latin cross composed of 6 unit squares and find its hull (among the 11 nets for a cube, some have lower area convex hulls than the latin cross which has hull area = 9 units). Not sure if this is in general a good way to get a min area or min perimeter convex wrapper.

On the same note, what is the best least area(perimeter) wrapper (convex or otherwise) of a sphere? This page might give a clue. If convexity is not demanded, one can have a many pointed star wrapper whose area arbitrarily approaches that of the sphere itself. The convex hull of this wrapper is a circular region; if we use this disk as a wrapper, there will be plenty of wastage. But are there no more economical convex wrappers for the sphere?

One can ask for convex shapes for which the least area rectangular wrapper and the least perimeter rectangular wrapper are as different as possible.

And for what types of 'wrappees' will the least area and/or least perimeter convex wrappers of any given 3d body have smooth boundaries?

Another way to approach this problem area is to ask questions like: Given a square (or circular or whatever) sheet of paper, which is the max volume 3d body (convex or not necessarily convex) that can be wrapped by the sheet - crumpling and folding and gluing allowed but no tearing or stretching. Most such questions might be open, somewhat like the well-known paper bag or teabag problem.

Let me also link this discussion page: https://mathoverflow.net/questions/347122/trapping-3d-regions-with-sheets-of-paper