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$?
 A: 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.
alt text http://dl.dropbox.com/u/5390048/TilingSlabs.jpg
