2
$\begingroup$

Most sphere/circle/square-packing problems are interested in the highest possible packing density, or the average density of a random packing. I am interested in what is the worst that one can do, for circles, squares, etc. For nontriviality, I am assuming the packing is maximal, in the sense that no one shape can be added to the packing anywhere without overlapping some shape that already exists.

Given a plane shape $S$, what is the (limiting) smallest possible packing density of a maximal packing of the plane with the shape $S$?

For squares, I thought at first that the answer might be $1/2$, as the following picture indicates.

A checkerboard pattern of pink squares with a black outline on a white background. The square are partially shifted around so that the white spaces are slightly smaller than the pink squares.

But after thinking about it a little longer, I realized you could get as low as $1/4$, as the following image shows. I am not sure if this can be improved upon.

A pattern of pink squares with black outlines arranged in a regular grid on a white background. The squares are spaced far apart from each other. Several transparent squares with dashed red outlines arranged around the central pink square indicate that no other pink square can be inserted into the arrangement without intersecting another pink square.

And what about circles, and other shapes?

Edit: I just realized that the square can't be as far apart as in the above picture, or else you could fit a rotated square in the white space between four squares. If the radius of the squares is $1$, then the distance between them needs to be less than $\sqrt{2}$ to prevent this, which gives a density of $4/(2+\sqrt{2})^2 \approx 0.34314\ldots$

A pattern of pink squares with black outlines arranged in a regular grid on a white background. The squares are spaced far apart from each other. A transparent square with a red dashed outline is rotated 45 degrees and positioned in the white space between the corners of four pink squares.

$\endgroup$
1
  • $\begingroup$ Except for "And what about circles", I think this is basically a duplicate of Least efficient method of packing unit squares into a circle? except I can't mark as a duplicate because that question has no accepted answer. I found that as it was my first Google hit for least efficient square packing. $\endgroup$
    – Mark S.
    Commented Jul 24, 2022 at 3:36

1 Answer 1

Reset to default
1
$\begingroup$

Here is a partial answer for the case of circle packings, dependent on the fact that circles look the same no matter how you rotate them.

Let $B_1$ be the open unit ball of radius $1$ and suppose $C \subset \mathbb{R}^2$ is a set of points such that $\{B_1 + c : c \in C\}$ is a maximal circle packing. That means that for every $x \in \mathbb{R}^2$, if $x \notin C$ then there exists a $c \in C$ such that $(B_1 + x)\cap (B_1 + c) \neq \varnothing$, which implies $d(x,c) < 2$.

That means that $\{B_2 + c : c \in C\}$ is a collection which actually covers the whole plane. In a hypothetical extreme case where $\{B_2 + c : c \in C\}$ is actually a partition of $\mathbb{R}^2$ (impossible for actual circles), the density of the packing would be precisely $\pi(1)^2 / \pi(2)^2 = 1/4$.

This shows that $1/4$ is a lower bound for the density of any maximal plane packing by circles, but is there actually a maximal circle packing (resp. family of circle packings) which achieves (resp. approaches) this bound?

$\endgroup$

You must log in to answer this question.

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