TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Thursday, April 19, 2018

Semicircle Packing



Although circle packing has been extensively researched, packing semicircles (half-disks is probably a more precise word) seems almost unexplored. Having hit upon this question, I searched but could find just one webpage - with a lament that there are no pages on packing semicircles(https://math.stackexchange.com/questions/1401327/packing-problem-of-semicircles-into-rectangle).

A natural way to pack the plane with semicircles is by assembling pairs of them into circles and then packing the circles hexagonally. can one do better? maybe not. but not sure.

History (source Wiki):

Laszlo Fejes Toth "proved that a lattice pattern is the most efficient way to pack centrally symmetric convex sets on the Euclidean plane". Lagrange had earlier proved that "the highest-density lattice arrangement of circles is the hexagonal packing arrangement". Together we have the result that the best packing of circles in a plane is the hexagonal pack.

Doubt: Is it possible to generalize Fejes Toth's result to say (say!) "a lattice pattern is the best way to pack convex sets with an axis of reflection symmetry"? Such a deduction might take us to a quick resolution of the semicircle packing.

And of course, one can worry about packing quadrants, hemispheres (packing in 3d space), and then go from packing the entire plane to packing various special containers (one can visit, for instance, 'Erich's Packing center' with its hundreds of non-trivial variations on this problem)or to go from packing to covering .... !

----------------

Progress (April 21, 2018)

The question above was posed, back in 1971, by Fejes Toth himself. It is still not fully resolved (the 'pairing of semicircles' approach above is known to be clearly suboptimal). The problem is listed in section 1.5 of 'Research Problems in Discrete Geometry' (by Brass, Moser and Pach).

I had actually looked into this book but failed to spot it because I used semicircle, disk and half-disk as search keys - and the authors have used semidisk! The book doesn't mention the 3d analog of this question (packing hemispheres); is it that putting two hemispheres together to form a sphere and to form the hexagonal close-pack of them (Kepler!) will also be suboptimal in 3d?? 3D has lots more space than 2D (roughly speaking) so the hcp may be way off the mark.