Are there non-tiling polyhedra that pack arbitrarily well?

2011-01-25T03:14:02Z

The fact that an upper bound on the packing density $< 1$ has only recently been exhibited for regular tetrahedra in $\mathbb{R}^3$ (see this question) suggests that proving concrete bounds of this type can be quite difficult. My question is, can a polyhedron have arbitrarily good packings, but no perfect one? There seem to be three ways in which this could happen:

Existence of packings with a finite uncovered volume
Existence of packings with asymptotic density $1$
Existence of packings with asymptotic densities ${\rho_1, \rho_2, \rho_3,...} \rightarrow 1$.

Are any of these cases known to be possible or impossible for polyhedra that do not tile? What about polygons in $\mathbb{R}^2$?

Answer by Bill Thurston for Are there non-tiling polyhedra that pack arbitrarily well?

2011-01-25T03:59:59Z

The easy topo-logic of this question depends on what you mean by a perfect tiling.

If the definition of a perfect tiling is a collection of isometric images of the polyhedron with disjoint interiors and union equal to the whole space, it follows from compactness in the Hausdorff topology. Suppose you have a sequence of packings that cover all but fraction $\epsilon_i$ of the ball of radius $R_i$, where $\epsilon_i \rightarrow 0$ and $R_i \rightarrow \infty$. Now look at all balls of fixed radius $R$ inside each of the balls of radius $R_i$. If $R_i$ is large enough compared to $R$, we can find at least one such ball that is covered except for $2\epsilon_i$ of its volume. The space of ways to of place copies of the polyhedron with disjoint interiors to intersect a ball of radius $R$ is compact, so there is a limit of these where the full measure of the ball is covered. Since the complement is open, since it has measure 0 it is empty, and in fact the entire ball is covered. Since we can do this for any $R$, we can find such a tiling of the ball of radius $R$ that is extendible to any larger radius $S > R$, then take a limit of extensions to successively larger balls that are extendible to still larger balls, and in the end we get a tiling of $\mathbb E^n$.

If you're insisting, in the definition of a perfect tiling, that faces match with faces, then it's not possible even in $\mathbb E^2$. Start with a standard tiling by parallelograms. Now modify the parallelograms to put a matching key/keyhole on two of the opposite sides, and a key and keyhole on the other pair of opposite sides that have the same shape, but are in different positions along the edge. The parallelograms fit into rows with a row of keys on the top, and keyholes on the bottom. The rows can be fit together, vertices don't align with vertices. There are many variations on this idea. For instance, in $\mathbb E^3$, you can construct convex polyhedra that fit together to tile a slab, but where you can't align parallel slabs to match the faces.

Here's an example tile (more complicated than it needs to be, but to make the point), and a tiling that some might call imperfect.

Are there non-tiling polyhedra that pack arbitrarily well? - MathOverflow

Are there non-tiling polyhedra that pack arbitrarily well?

Answer by Bill Thurston for Are there non-tiling polyhedra that pack arbitrarily well?