Covering and Packing
coverage constants. How big must N equal disks be in order to
completely cover the unit disk? What about disks with sizes in
geometric progression? From MathSoft's favorite constants pages.
- Covering points by rectangles.
Stan Shebs discusses the problem of finding a minimum number of
copies of a given rectangle that will cover all points in some set,
and mentions an application to a computer strategy game.
This is NP-hard, but I don't know how easy it is to approximate;
most related work I know of is on optimizing the rectangle size for a cover
by a fixed number of rectangles.
triangles. Dan Asimov asks how large a triangle will fit into a
square torus; equivalently, the densest packing of equilateral triangles
in the pattern of a square lattice.
There is only one parameter to optimize, the angle of the triangle to
the lattice vectors; my answer
is that the densest packing occurs when
this angle is 15 or 45 degrees, shown below.
(If the lattice doesn't have to be square, it is possible to get density
2/3; apparently this was long known, e.g. see Fáry,
Bull. Soc. Math. France 78 (1950) 152.)
Asimov also asks for the smallest triangle that will always cover at least
one point of the integer lattice, or equivalently a triangle
such that no matter at what angle you place copies of it on an integer lattice,
they always cover the plane; my guess is that the worst angle is parallel
and 30 degrees to the lattice, giving a triangle with 2-unit sides
and contradicting an earlier answer to Asimov's question.
Packing Page. Erich Friedman enjoys packing geometric shapes into
other geometric shapes.
- Filling space with unit circles. Daniel
Asimov asks what fraction of 3-dimensional space can be filled by a
collection of disjoint unit circles. (It may not be obvious that this
fraction is nonzero, but a standard construction allows one to construct
a solid torus out of circles, and one can then pack tori to fill space,
leaving some uncovered gaps between the tori.) The geometry center has
information in several places on this problem, the best being an
describing a way of filling space by unit circles (discontinuously).
Honeybees, and Hexagons. Thomas Hales proves the optimality of
bees' hexagonal honeycomb structure. Ivars Peterson, Science News Online.
- Hyperbolic packing of convex bodies.
William Thurston answers a question of
Greg Kuperberg, on
whether there is a constant C such that every convex body in the
hyperbolic plane can be packed with density C. The answer is no -- long
skinny bodies can not be packed efficiently.
- Kelvin conjecture counterexample.
Evelyn Sander forwards news about the discovery by Phelan and Weaire
of a better way to partition space
into equal-volume low-surface-area cells.
Kelvin had conjectured that the truncated octahedron provided the optimal
solution, but this turned out not to be true.
See also Ruggero Gabbrielli's comparison of equal-volume partitions and
- Packing Ferrers Shapes.
Alon, Bóna, and Spencer show that one can't cover very much of an n by p(n)
rectangle with staircase polyominoes (where p(n) is the number of these
Mark Michell investigates the problem of arranging pentominoes into
rectangles of various (non-integer) aspect ratios,
in order to saw the largest possible pieces from a given size piece of
- Packing rectangles into similar rectangles.
A problem of the month from Erich Friedman's Math Magic site:
how small an aspect-ratio-r rectangle can contain n unit-area
As you might hope for in a problem dealing with aspect ratios
of rectangles, the golden rectangle does show up, as one of the
breakpoints in the size function for packing five smaller rectangles.
Tetrahedrons, and Closing in on a Perfect Fit. Elizabeth Chen and
others use experiments on hundreds of D&D dice to smash previous
records for packing density.
- Packings in Grassmannian spaces, N. Sloane, AT&T.
How to arrange lines, planes, and other low-dimensional spaces into
smoothed octagon. A candidate for the symmetric convex shape that
is least able to pack the plane densely.
What is the longest path of unit-length line segments, connected
end-to-end with angles that are multiples of some fixed d,
and that can be covered by a square of given size?
- Sphere packing and kissing numbers.
How should one arrange circles or spheres
so that they fill space as densely as possible?
What is the maximum number of spheres that can simultanously touch
packing. Mathematica implementation of the Chen-Engel-Glotzer packing
of space by regular tetrahedra, the densest known such packing to date.
From the Geometry Junkyard,
and recreational geometry pointers.
Send email if you
know of an appropriate page not listed here.
from a common source file.