1
$\begingroup$

A (translational) packing of a convex compact subset (with non-empty interior) $\mathcal C$ of $\mathbb R^d$ is a union of translated non-overlapping (but perhaps touching) copies of $\mathcal C$.

The (translational) packing density of $\mathcal C$ is the maximal proportion of $\mathbb R^d$ occupied by a suitable packing. The best packing density is $1$ and is achieved if and and only if $\mathcal C$ tiles $\mathcal R^d$. (The proof is a compacity argument.)

Is something known about convex compact sets achieving the worst packing density for a given dimension? (The worst possible packing-density in a fixed dimension is always strictly positive: The set of all convex compact sets is compact, up to the action of the affine group.)

I suspect that the worst case for $d=2$ are triangles (probably achieving only a translational packing density of $1/2$). (I guess that the $2$-dimensional case is quite accessible and has been studied by somebody.)

Added correction: (based on the reply by RavenclawPrefect) Triangles are indeed the worst case in dimension $2$ but a packing density of $2/3$ can be achieved: Surround every triangle by six touching triangles such that every intersection between two triangles involves a vertex of one triangle and the midpoint of an edge of the other triangle. (End of added correction)

More generally, simplices should be fairly bad in all dimensions.

Is there an interesting lower bound for packing densities for simplices? (The notion is affine, all simplices have thus the same packing density and considering the simplex defined by all points with coordinate-sum $\leq 1$ in $[0,1]^d$ shows that the packing-density of a $d$-dimensional simplex is at least $1/d!$.)

Final remark: The case of packing densities for (Euclidean) balls is a well-studied subject. However exact values are only known in very few cases. The lack of knowledge in high dimensions is irritating even in this simple case.

$\endgroup$

1 Answer 1

2
$\begingroup$

I believe this is not in general known for $d>2$. Chapter 2 of the Handbook of Discrete and Computational Geometry provides some pretty detailed information about translational packing density, which in their notation is $\delta_T$. In particular, we have that the translational packing density of the regular tetrahedron is between $18/49\approx0.3673$ and $0.3745$ (an unusually tight range, compared to what we know for most shapes). I am not sure if this is the smallest known, but I can't think of anything known to perform worse.

The quote on page 30

One could expect that the restriction to arrangements of translates of a set means a considerable simplification. However, this apparent advantage has not been exploited so far in dimensions greater than $2$.

seems relevant here.

Things are a little better known for lattice packing densities, where we further stipulate that the centers of the bodies form a lattice. We don't actually know any convex bodies where lattice packings aren't optimal, but I think in general we also don't have proofs of this optimality.

However, in dimension $2$ we do have an exact answer: you are correct that triangles uniquely attain the minimum, although that minimum value is $2/3$. See Theorem 1.1 from this paper.

$\endgroup$
1
  • $\begingroup$ I accept your answer: It contains two interesting references and I think one cannot hope for much more. $\endgroup$ Commented Aug 3, 2021 at 19:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .