Unique question about packing problem

Question

I added the related pages from part 3 of the book: combinatorial geometry by János Pach,Pankaj K.Agarwal (1995) (which is not available on net so I added them as pictures).

A. Prove that one can always find a packing $Ç$ of the plane with congruent copies of a convex disc $C$ whose density $d(Ç,R^2)$ exists and is equal to $\delta(C)$. Similarly show that there is a Lattice packing $Ç$ with $d(Ç,R^2)=\delta_L(C)$.

B.construct a packing $Ç$ of unit discs and two convex discs $P,P'$ such that $lim_{r\to \infty} d(Ç,P(r)) \neq lim_{r\to \infty} d(Ç,P'(r))$.

Hints: Part A:To prove the first statement, construct a packing $C_n$ of congruent copies of $C$ in the disc $D(n)$ with density $d(C_n,D(n))\geq \delta(C)-O(1)/n$

For every n choose a subsequence $n_1,n_2,...$ such that $C_{n_i}$ converges when restricted to $D(1)$ as $i\to \infty$ . From this choose a subsequence for which $C_n$ converges when restricted to $D(2)$ and so on. Show that the limit packing meets the requirements.

For part B: Let $Ç$ be the densest packing of unit discs in a cone. Choose $P$ and $P'$ to be circular disc and a regular triangle respectively.

Can you kindly help me to understand this (I'm a beginner in this field).

1.(https://i.stack.imgur.com/2k1mz.jpg)

2.(https://i.stack.imgur.com/ZEdCp.jpg)

3.(https://i.stack.imgur.com/fhhvM.jpg)

4.(https://i.stack.imgur.com/WIVsz.jpg)

5.(https://i.stack.imgur.com/B2O4m.jpg)

6.(https://i.stack.imgur.com/ZuXvX.jpg)

Many thanks.

Answer 1

I'm adding another answer, since my first is already pretty dense and I think it would be contextually useful to leave it up--- at least to make the comments make sense. If this is a StackExchange faux pas, apologies.

Lemma: Fix some convex disc $C$ and $R \subseteq \mathbb{R}^2$. Then there is a packing $P$ which achieves an arbitrary density between $0$ and $\delta(C)$. That is to say, there is a packing $P$ so that $d(P,R) = r \in \mathbb{R}$, where $0 \leqslant r \leqslant \delta(C)$.

There are many ways to prove this, but I think if you want to make this rigorous a separation into cases and then IVT via translating a specific copy of $C$ through the boundary to increase density.

Proof of A:

Fix some convex disc $C$, and create an infinite family of packings $C_n$ so that:

$$d(C_n, D(n)) \geqslant \delta(C) - \frac{O(1)}{n}$$

for each $n$. Such a construction is justified by the lemma, since $O(1)/n > 0$. Moreover, the interval $[0,A(D(n))]$ is compact, so we choose a subsequence which converges in $D(1)$, then one which converges in $D(2)$ from that subsequence, and so on forever. Now let:

$$P = \lim_{n \rightarrow \infty} C^\ast_n$$

Where $C^\ast_n$ is the limiting sequence. I claim that $P$ is our desired packing. Indeed:

$$\delta(C) \geqslant \lim_{n \rightarrow \infty} d(C^\ast_n, D(n)) \geqslant \delta(C) - \lim_{n \rightarrow \infty} \frac{O(1)}{n}$$

since the limiting sequence converges in all $D(n)$ and has the bounds in all $D(n)$. As $\lim_{n\rightarrow \infty} O(1)/n$ goes to $0$, we have what we desired.

See if you can formulate something for the lattice packing.

Proof of B:

Fix our region $Q$ a convex cone of angle $\pi/3$ whose vertex is at the origin, and let $P$ be the densest packing of $Q$ with unit discs.

Then letting $P(r)$ be the disc $d(0,x) \leqslant r$, we can see immediately that $d(P,P(r)) \leqslant 1/6$ for large $r$.

Now let $P'(r)$ be an equilateral triangle with vertex at the origin and two legs on the boundary of $Q$. Since the angle of $Q$ is $\pi/3$, $P'(r)$ will always be in $Q$, and as this is the densest packing, it follows that $$\lim_{n \rightarrow \infty} d(P,P'(r)) = \frac{\pi}{\sqrt{12}}$$

by the results mentioned in the textbook.

As $\pi/\sqrt{12} > 1/6$, their densities as $r \rightarrow \infty$ are different.

EDIT: Here is an image of the cone and the disc.

Answer 2

EDIT: I'm leaving this post as context. See my comment to Usermat about my mistake.

For A:

I assume you have verified all of the results on the pages, or else are comfortable using them.

Note that page 5 gives us $$\delta(P) = \max_{P}d(P,\mathbb{R}^2)$$

for $P$ a packing. Hence for any packing $P$, it follows that $d(P,\mathbb{R}^2) \leqslant \delta(P)$. We wish to find a packing $X$ which satisfies $d(X,\mathbb{R}^2) \geqslant \delta(X)$, which will prove the result. This implies we need an optimal packing, which the textbook has supplied us with in the form of the packing in Figure 3.1. After all, the result of Thue says that $\overline{d}(P,\mathbb{R}^2) \leqslant \pi/\sqrt{12}$ for any packing, and so $d(P,\mathbb{R}^2) \leqslant d(X,\mathbb{R}^2) = \pi/\sqrt{12}$ for the greatest density packing $X$. Then $\max_Pd(P,\mathbb{R}^2) \leqslant d(X,\mathbb{R}^2)$ follows from this inequality holding for all $P$ packings, which is the reverse inequality we sought to show.

The second result of A follows from Corollary 3.6.

EDIT: This was a proof for discs in the normal usage of the term. The response to my comment in the post has a convex disc defined as a convex compact set with nonempty interior, so the proof does not strictly apply. In particular, the step where we show that $X$ is maximal no longer counts, because I chose a circle packing.

In general, I think that a packing of centrally symmetric hexagons $H$ will suffice. In fact, as this tiles the plane then the density will be 1, hence is easily seen to be maximal.

SECOND EDIT (In response to OP): Here is how I would write the proof.

Let $H$ be a collection of centrally symmetric hexagons which tile the plane. We wish to show:

$$d(H,R^2) = \delta(H)$$

which we will demonstrate via double inclusion (this method has many names).

The first direction is to show $d(H,R^2) \leqslant \delta(H)$. Indeed, it can be shown that $\delta(H) = \max d(H, R^2)$, where the maximum ranges over all packings with the elements of our packing. As our particular packing $H$ is one such packing, its density is at most $\delta(H)$.

The second direction is to show $d(H, R^2) \geqslant \delta(H)$. Here the choice of $H$ is relevant (notice that it was not used in the first direction), and in fact since $H$ is a plane tiling, the density of $H$ is $1$. It is easy to see that $d(Q,R^2)$ for any packing $Q$ is bounded above by $1$, hence $\delta(Q) \leqslant 1$ for any such collection of convex discs. Picking $H$ in particular, it follows that $\delta(H) \leqslant 1 = d(H, R^2)$.

Then as $d(H,R^2) \leqslant \delta(H) \leqslant d(H,R^2)$, by double inclusion we have what we wished to prove.

For a lattice packing, we note that since the elements of $H$ regularly tile the plane, the packing $H$ forms a lattice packing as well, and by Corollary 3.6, $\delta(H) = \delta_L(H)$. Hence:

$$d(H,R^2) = \delta(H) = \delta_L(H)$$

which is what we had to show.