Covering and Packing

• Circular 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.

• Equilateral 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.

  

• Erich's 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 article describing a way of filling space by unit circles (discontinuously).

• Hales, 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 JavaView foam models.
  

• 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 shapes).

• Packing polyominoes. 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 wood.

• 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 aspect-ratio-r rectangles? 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.

• Packing 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 higher-dimensional spaces.

• The smoothed octagon. A candidate for the symmetric convex shape that is least able to pack the plane densely.

• Snakes. 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 another sphere?

• Tetrahedra 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, computational and recreational geometry pointers.
Send email if you know of an appropriate page not listed here.
David Eppstein, Theory Group, ICS, UC Irvine.
Semi-automatically filtered from a common source file.