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

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$?

-
No, by compactness principle (the same one as shows that if you can tile an arbitrarily large ball, you can tile the whole space). –  fedja Jan 25 '11 at 3:31

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.

-
As I read approaching the end, I wanted more and more one of your great pictures :) –  Mariano Suárez-Alvarez Jan 25 '11 at 4:14
Okay, I know, I felt guilty not putting it in at the end. I'll do it if it doesn't take me too long. –  Bill Thurston Jan 25 '11 at 4:22
Great! :) $\mbox{}$ –  Mariano Suárez-Alvarez Jan 25 '11 at 4:47
Yes, I did mean the first kind of perfect tiling (shapes w/ disjoint interiors whose union is the entire space). I understand the first part of the argument: if you can fill a ball of radius $R$ with unpacked fraction arbitrarily close to zero, you can fill it perfectly. How does it follow that there is a perfect tiling of the entire space? I.e., what is the justification for taking "a limit of extensions to successively larger balls that are extendible to still larger balls"? –  mjqxxxx Jan 25 '11 at 15:37
@mjqxxxx: Sorry for being cryptic. So: for each $R$, there are perfect tilings of the ball of radius $R$. These might not be extendible to larger balls, but we can take a sequence of perfect tilings of the ball of radius $S$ restricted to the ball of radius $R_1$, and these have somelimit that can be extended to any concentric larger ball. Choose one of these. Inductively, given $R_i$ look at extensions to a larger ball, say $R_i+1 = 2 R_1$ that can be extended to still larger balls $S$, an choose a limit point of these. The increasing union is the plane. –  Bill Thurston Jan 25 '11 at 18:35