# On exact covering with unit disks

Ji Hoon Chun  Technische Universität Berlin
<EMAIL_ADDRESS>Christian Kipp  Technische Universität Berlin
<EMAIL_ADDRESS>Sandro Roch Technische Universität Berlin
<EMAIL_ADDRESS>
###### Abstract

We study the problem of covering a given point set in the plane by unit disks
so that each point is covered exactly once. We prove that $17$ points can
always be exactly covered. On the other hand, we construct a set of $657$
points where an exact cover is not possible.

##  1 Introduction

In 2008, Inaba [11] introduced the following puzzle about covering sets of
points in the plane:

Show that any set of $\mathit{10}$ points in $\mathbb{R}^{2}$ can be covered
by nonoverlapping unit disks.

Inaba solved this puzzle [12, 20] with an elegant probabilistic argument (see
Appendix A for a deterministic version). In this article, we study a relaxed
version of this covering problem. Given a point set $X\subset\mathbb{R}^{2}$,
can we find a family $\mathscr{D}$ of not necessarily disjoint unit disks so
that each point $\mathbf{x}\in X$ is contained in exactly one disk
$D\in\mathscr{D}$? We call such a family an exact cover of $X$. For example,
in Figure 1(a), the two red disks form an exact cover of the four blue points.

(a)

(b)

Figure 1: Left: Primal solution (exact covering set). Right: Dual solution
(exact hitting set).

Let
$B^{2}\coloneqq\left\\{\mathbf{x}\in\mathbb{R}^{2}\,\middle|\,\left\|\mathbf{x}\right\|<1\right\\}$,
where $\|\cdot\|$ denotes the Euclidean norm. We define an (open) disk with
center $\mathbf{c}\in\mathbb{R}^{2}$ and radius $r>0$ as the set
$D_{\mathbf{c},r}\coloneqq\mathbf{c}+rB^{2}$; if $r=1$ we call it the unit
disk and write $D_{\mathbf{c}}$.

######  Definition 1.1.

Let $\sigma_{2}$ be the largest $n\in\mathbb{N}$ such that any set of $n$
points in the plane can be covered by disjoint unit disks. Let
$\widehat{\sigma}_{2}\in\mathbb{N}$ be the corresponding number for the
relaxed problem involving exact covers.

As a covering using disjoint disks is also an exact covering, we have the
basic relationship of $\widehat{\sigma}_{2}\geq\sigma_{2}$. The current best
known bounds for $\sigma_{2}$ are $12\leq\sigma_{2}\leq 44$ [1]. Aloupis,
Hearn, Iwasawa, and Uehara (2012) [1] improved Inaba’s lower bound to
$\sigma_{2}\geq 12$ through a careful analysis of the probabilistic method on
one-dimensional slices of the plane. In the other direction, $\sigma_{2}$ is
finite: Intuitively, with a dense enough arrangement of points, this problem
becomes similar to the problem of covering the entire set
$\operatorname{conv}X$, which is impossible using disjoint disks. Specific
upper bounds were reduced in rapid succession from $\sigma_{2}<60$ by Winkler
(2010) [20] to $\sigma_{2}<55$ by Elser (2011) [7] and $\sigma_{2}<53$ by
Okayama, Kiyomi, and Uehara (2012) [18]. Most recently, Aloupis, Hearn,
Iwasawa, and Uehara (2012) [1] proved $\sigma_{2}<50$ “by hand” and
demonstrated $\sigma_{2}<45$ using computer calculations.

###  1.1 Results

In Section 2, we build on some of the mentioned works on lower bounds to
establish the following lower bound on $\widehat{\sigma}_{2}$:

######  Theorem 1.2.

We have $\widehat{\sigma}_{2}\geq 17$.

The finiteness of $\widehat{\sigma}_{2}$ can be deduced by a similar argument
as for the finiteness of $\sigma_{2}$. In Section 3 we construct a close
arrangement of points that cannot be exactly covered, leading to the following
(rather weak) upper bound on $\widehat{\sigma}_{2}$:

######  Theorem 1.3.

We have $\widehat{\sigma}_{2}<657$.

For the full proofs of Theorem 1.2 and Theorem 1.3 we refer to Sections 2 and
3 respectively.

###  1.2 Relation between exact covering and exact hitting

We denote by $\mathscr{X}$ the collection of all finite point sets in
$\mathbb{R}^{2}$. A point $\mathbf{x}\in\mathbb{R}^{2}$ is contained in a unit
disk $D_{\mathbf{c}}$ centered at $\mathbf{c}\in\mathbb{R}^{2}$ if and only if
$\mathbf{c}$ is contained in the unit disk $D_{\mathbf{x}}$ centered at
$\mathbf{x}$. By this simple observation, the problem of exactly covering some
given $X\in\mathscr{X}$ by unit disks (primal problem) becomes equivalent to
the following dual problem: Let
$\mathscr{D}_{X}\coloneqq\left\\{D_{\mathbf{x}}\,\middle|\,\mathbf{x}\in
X\right\\}$; find a $P\in\mathscr{X}$ such that each disk
$D\in\mathscr{D}_{X}$ contains exactly one point $\mathbf{p}\in P$. See Figure
1(b) for an example of the dual problem. In the literature, such a set $P$ is
also called an exact hitting set. A dual solution $P$ yields the solution
$\mathscr{D}\coloneqq\left\\{D_{\mathbf{p}}\,\middle|\,\mathbf{p}\in
P\right\\}$ to the exact covering problem. Vice versa, a solution
$\mathscr{D}$ to the exact covering problem gives a solution to the dual
problem by taking the disk centers.

In the dual perspective, the boundary circles of the disks $\mathscr{D}_{X}$
decompose the plane into cells. Observe that all points in a given cell are
contained in the same set of disks, so the exact position of a dual solution
point $\mathbf{p}\in P$ is irrelevant. Hence, it is sufficient to select a set
of cells so that each $D\in\mathscr{D}_{X}$ contains exactly one selected
cell. In the example of Figure 1(b), the two red shaded cells form a solution.
This observation shows that the solution space for the dual problem and for
the exact covering problem is in fact discrete, and methods such as Knuth’s
Algorithm X (see [15] or Section 7.2.2.1 in [16]), integer programming, or SAT
solvers (see [14]) can be used.

##  2 A lower bound

We exclude the following trivial case from our proofs in this section: If $X$
lies on a line then $X$ can be covered by disjoint disks. Denote by
$\mathscr{X}^{\prime}$ the subset of $\mathscr{X}$ that excludes every point
set on a line. To prove Theorem 1.2, we have to show that all
$X\in\mathscr{X}^{\prime}$ with $\lvert X\rvert\leq 17$ can be exactly
covered. We combine three separate components on top of Inaba’s original
probabilistic proof. In Subsection 2.1 we show that
$\widehat{\sigma}_{2}\geq\sigma_{2}+4$. In Subsection 2.2 we obtain
$\widehat{\sigma}_{2}\geq 16$ using a covering version of Betke, Henk, and
Wills’s parametric density [3], and $\widehat{\sigma}_{2}\geq 17$ by showing
that in some cases, a disk $D$ that overlaps with $\operatorname{conv}X$ can
be removed from an exact cover $\mathscr{D}$ of $X$ so that
$\mathscr{D}\left\backslash\,\left\\{D\right\\}\right.$ is still an exact
cover of $X$.

In this section, we denote the vertices of $\operatorname{conv}X$ by
$\mathbf{v}^{1},\ldots,\mathbf{v}^{k}$. We use subscripts to denote the
coordinates of a vector, so for example
$\mathbf{v}^{i}=\begin{pmatrix}v_{1}^{i}\\\ v_{2}^{i}\end{pmatrix}$.

###  2.1 Boundary points

######  Definition 2.1.

Let $X\in\mathscr{X}$ and $\mathbf{v}\in X$. The point $\mathbf{v}$ is a
boundary point of $X$ if $\mathbf{v}$ is on the boundary of
$\operatorname{conv}X$.

Let $X\in\mathscr{X}$ and $\mathbf{v}^{1},\ldots,\mathbf{v}^{k}$ be the
boundary points of $X$. László Kozma (private communication) observed that a
covering $\mathscr{D}^{\prime}$ of the non-boundary points
$X^{\prime}\coloneqq
X\left\backslash\,\left\\{\mathbf{v}^{1},\ldots,\mathbf{v}^{k}\right\\}\right.\\!$
by disjoint disks can always be extended to an exact cover of $X$. A boundary
point $\mathbf{v}^{i}$ is covered by at most one disk in
$\mathscr{D}^{\prime}$ because the disks are disjoint. If $\mathbf{v}^{i}$ is
not already covered by $\mathscr{D}^{\prime}$, then it can be covered by a new
disk which contains $\mathbf{v}^{i}$ but no other point of $X$. The resulting
disk configuration yields an exact cover $\mathscr{D}$ of $X$ (Figure 2). In
particular, if $\left|X\right|\leq\sigma_{2}+k$ then $X$ can be exactly
covered. We refer to this strategy as the Extension Argument:

######  Lemma 2.2 (Extension Argument).

Let $X\in\mathscr{X}$ and $k$ be the number of boundary points of
$\operatorname{conv}X$.

  1. 1.

If $\left|X\right|\leq\sigma_{2}+k$ then $X$ can be exactly covered.

  2. 2.

If $k\leq 2$ then $X$ can be exactly covered regardless of $\left|X\right|$.

  3. 3.

We have $\widehat{\sigma}_{2}\geq\sigma_{2}+3$.

Figure 2: Proof idea of the Extension Argument 2.2. We extend the red disjoint
disk covering of the non-boundary points by adding a new orange disk at each
uncovered boundary point. The new disks may overlap each other or existing
disks.

###### Proof.

As $X$ can be assumed to not lie on a line, we have $k\geq 3$. Let
$X\in\mathscr{X}$ with $\left|X\right|\leq\sigma_{2}+k$. The set
$X^{\prime}\in\mathscr{X}^{\prime}$ has at most $\sigma_{2}$ points, so there
exists a collection $\mathscr{D}^{\prime}$ of disjoint disks that covers
$X^{\prime}$.

For each vertex $\mathbf{v}^{i}$ of $X$, consider the two cases below.

  1. 1.

If $\mathbf{v}^{i}$ is already covered by some disk in $\mathscr{D}^{\prime}$,
then do nothing.

  2. 2.

If $\mathbf{v}^{i}$ is not covered by any disk in $\mathscr{D}^{\prime}$, then
add a new disk that covers $\mathbf{v}^{i}$ but no other point of $X$. Such a
disk can always be found because $\operatorname{conv}X$ is convex and $B^{2}$
is strictly convex, but it may overlap with some existing disk(s) in
$\mathscr{D}^{\prime}$ (Figure 2).

The cover $\mathscr{D}\coloneqq\mathscr{D}^{\prime}\cup\left\\{\text{all new
disks from case 2}\right\\}$ is an exact cover of $X$.

The third part of the Extension Argument is a direct consequence of the first
two parts. ∎

######  Remark 2.3.

The Extension Argument 2.2, along with its generalization below (Lemma 2.5),
cannot be applied to extend an exact cover $\mathscr{D}^{\prime}$ of
$X^{\prime}$ to an exact cover of $X$. In this case, the disks of
$\mathscr{D}^{\prime}$ are allowed to overlap, so some $\mathbf{v}^{i}$ may be
contained in more than one disk of $\mathscr{D}^{\prime}$.

The Extension Argument improves the basic inequality
$\widehat{\sigma}_{2}\geq\sigma_{2}$ to
$\widehat{\sigma}_{2}\geq\sigma_{2}+3$. Hence this lemma, combined with
Inaba’s and Aloupis, Hearn, Iwasawa, and Uehara’s results, obtains
$\widehat{\sigma}_{2}\geq 13$ and $\widehat{\sigma}_{2}\geq 15$ respectively.
These lower bounds are limited by the case where $\operatorname{conv}X$ is a
triangle, since otherwise $X$ has at least four boundary points. Therefore, we
wish to relax Definition 2.1 so that every $X\in\mathscr{X}^{\prime}$ has at
least four “generalized boundary points” that behave like boundary points, or
can be exactly covered regardless of $\left|X\right|$.

######  Definition 2.4.

Let $X\in\mathscr{X}$ and $\mathbf{b}\in X$. The point $\mathbf{b}$ is a
generalized boundary point of $X$ if there exists a
$\mathbf{c}\in\mathbb{R}^{2}$ such that $X\cap
D_{\mathbf{c}}=\left\\{\mathbf{b}\right\\}$.

All vertices and boundary points of $X$ are generalized boundary points of
$X$. Let $\mathbf{b}^{1},\ldots,\mathbf{b}^{k}$ be the generalized boundary
points of $X$, and write $X^{\prime\prime}\coloneqq
X\left\backslash\,\left\\{\mathbf{b}^{1},\ldots,\mathbf{b}^{k}\right\\}\right.$.

Let $k\in\mathbb{N}_{0}$. For convenience, we write
$\widehat{\sigma}_{2}\left(k\right)$ to denote the largest $n\in\mathbb{N}$
such that all sets in $\mathscr{X}$ with at most $n$ points, at least $k$ of
which are generalized boundary points, can be exactly covered. For any
$k^{\prime}\geq k\geq 0$, we have
$\widehat{\sigma}_{2}\left(k^{\prime}\right)\geq\widehat{\sigma}_{2}\left(k\right)=\widehat{\sigma}_{2}\left(0\right)=\widehat{\sigma}_{2}$.

######  Lemma 2.5 (Generalized Extension Argument).

Let $X\in\mathscr{X}^{\prime}$ and $k$ be the number of generalized boundary
points of $\operatorname{conv}X$.

  1. 1.

If $\lvert X\rvert\leq\sigma_{2}+k$ then $X$ can be exactly covered. (That is,
$\widehat{\sigma}_{2}\left(k\right)\geq\sigma_{2}+k$.)

  2. 2.

If $k\leq 3$ then $X$ can be exactly covered regardless of $\left|X\right|$.

  3. 3.

We have $\widehat{\sigma}_{2}\geq\sigma_{2}+4$.

Thanks to our definition of a generalized boundary point, the proof of Part 1
of the Generalized Extension Argument is fundamentally the same as the proof
of the corresponding claim in the Extension Argument. The main difference is
that to avoid a generalized boundary point being covered by more than one new
disk, we add these new disks one at a time instead of all at once.

###### Proof of the Generalized Extension Argument, Part 1.

Let $\mathbf{b}^{1},\ldots,\mathbf{b}^{k}$ be the generalized boundary points
of $X$. Let $X_{0}\coloneqq X^{\prime\prime}$ and $X_{i}\coloneqq
X_{i-1}\cup\left\\{\mathbf{b}^{i}\right\\}$ for
$i\in\left\\{1,\ldots,k\right\\}$. The set $X_{0}\in\mathscr{X}^{\prime}$ has
at most $\sigma_{2}$ points, so there exists a disjoint covering
$\mathscr{D}_{0}$ of $X_{0}$.

We recursively show that each $X_{i}$ can be exactly covered. Let
$i\in\left\\{1,\ldots,k\right\\}$. Suppose that we have an exact cover
$\mathscr{D}_{i-1}\supseteq\mathscr{D}_{0}$ of $X_{i-1}$. Consider the
generalized boundary point $\mathbf{b}^{i}$.

  1. 1.

If $\mathbf{b}^{i}$ is covered by some disk in $\mathscr{D}_{i-1}$, then do
nothing. The collection $\mathscr{D}_{i}\coloneqq\mathscr{D}_{i-1}$ is already
an exact cover of $X_{i}$.

  2. 2.

If $\mathbf{b}^{i}$ is not covered by any disk in $\mathscr{D}_{i-1}$, then
add a new disk $D_{i}$ that covers $\mathbf{b}^{i}$ but no other point of $X$.
Such a disk can always be found by the definition of a generalized boundary
point. The collection
$\mathscr{D}_{i}\coloneqq\mathscr{D}_{i-1}\cup\left\\{D_{i}\right\\}$ is an
exact cover of $X_{i}$.

Setting $i=k$ finishes the proof. ∎

The Generalized Extension Argument combined with Aloupis, Hearn, Iwasawa, and
Uehara’s lower bound implies $\widehat{\sigma}_{2}\geq 16$.

For the remainder of this subsection, assume that $X\in\mathscr{X}^{\prime}$
has at least four points, since if $X$ has three or fewer points, then there
is nothing to prove. If $\operatorname{conv}X$ is a triangle, then we write
$T\coloneqq\operatorname{conv}X$ and $T^{\prime}\coloneqq
T\left\backslash\,\left\\{\mathbf{v}^{1},\mathbf{v}^{2},\mathbf{v}^{3}\right\\}\right.$,
where $\mathbf{v}^{1}$, $\mathbf{v}^{2}$, and $\mathbf{v}^{3}$ are its three
vertices ($X$ may have additional boundary points). Let $R_{T}$ be the
circumradius of $T$.

Our proof of Part 2 of the Generalized Extension Argument consists of a more
involved case analysis than for the Extension Argument. Let
$X\in\mathscr{X}^{\prime}$. The following cases envelop all the possibilities
for a triangular convex hull $\operatorname{conv}X$, ordered by descending
side lengths and circumradius.

######  Lemma 2.6.

If at least one side of $T$ has length at least $2$, then $X$ has at least
four generalized boundary points. (In this case, $R_{T}\geq 1$.)

######  Lemma 2.7.

If all sides of $T$ have length less than $2$ and $R_{T}>1$, then $X$ has at
least four generalized boundary points.

######  Lemma 2.8.

If all sides of $T$ have length less than $2$ and $R_{T}=1$, then $X$ can be
covered by four unit disks.

###### Proof.

The interior of the circumcircle $D$ of $T$ is a unit disk that covers
$T^{\prime}$. Each vertex of $T$ can be covered by a separate unit disk as in
the proof of the Extension Argument 2.2. ∎

######  Lemma 2.9.

If all sides of $T$ have length less than $2$ and $R_{T}<1$, then $X$ can be
covered by one unit disk.

###### Proof.

Cover the circumcircle of $T$ with a unit disk. ∎

The first two lemmas show that for a “large” triangle we can always find one
additional generalized boundary point $\mathbf{b}\in X^{\prime}$. This point
is, roughly speaking, the closest non-vertex of $X$ to the longest edge of
$\operatorname{conv}X$. Since the proofs are lengthy, we leave them for later
in this section. A “small” triangle $T$ lacks room for a fourth generalized
boundary point since its vertices are too close to each point of $X$
(including the other vertices). However, the other two lemmas show that every
small triangle can be exactly covered by a fixed number of disks independently
of $\left|X\right|$.

###### Proof of the Generalized Extension Argument 2.5, Parts 2 and 3.

Since $X\in\mathscr{X}^{\prime}$ has $k\leq 3$ generalized boundary points,
its convex hull of $X$ must be a triangle. If $R_{T}>1$ then $X$ has four
generalized boundary points by Lemmas 2.6 and 2.7, so $R_{T}\leq 1$. So $X$
can be exactly covered by Lemmas 2.8 and 2.9.

As before, Part 3 of the Generalized Extension Argument is a direct
consequence of Parts 1 and 2. ∎

The main idea for the proof of Lemma 2.6 is as follows. Suppose that the
longest side $\overline{\mathbf{v}^{1}\mathbf{v}^{2}}$ of $T$ has length
greater than or equal to $2$. Place a unit disk $D$ outside $T$ and push it
through $\overline{\mathbf{v}^{1}\mathbf{v}^{2}}$ from below, without touching
either $\mathbf{v}^{1}$ or $\mathbf{v}^{2}$, until it reaches a point
$\mathbf{b}\in X^{\prime}$. If chosen correctly, $D$ will cover $\mathbf{b}$
but no other point of $X$, hence $\mathbf{b}$ is the desired fourth
generalized boundary point.

We specify how this generalized boundary point is chosen using the following
technical definition.

######  Definition 2.10.

Let $X\in\mathscr{X}^{\prime}$ satisfy the hypothesis of Lemma 2.6. Without
loss of generality, position $X$ so that
$\overline{\mathbf{v}^{1}\mathbf{v}^{2}}$ is the longest side of
$T=\operatorname{conv}X$, $\mathbf{v}^{1}=\begin{pmatrix}-v\\\
\hphantom{+}0\end{pmatrix}$ and $\mathbf{v}^{2}=\begin{pmatrix}v\\\
0\end{pmatrix}$ for some $v\geq 1$, and $v_{2}^{3}>0$. Let $t\geq-1$. Define
the bulldozer111The term “bulldozer” and its abbreviation are from [10], in
particular slide 23. $\operatorname{BD}\left(X,t\right)$ by (see Figure 3)

$\operatorname{BD}\left(X,t\right)\coloneqq\bigcup_{c\in\left[-\left(v-1\right),v-1\right]}\left(\begin{pmatrix}c\\\
t\end{pmatrix}+B^{2}\right).$

We will show that if $\overline{\mathbf{v}^{1}\mathbf{v}^{2}}$ has length at
least $2$, i.e., $v\geq 1$, then by increasing $t$, the bulldozer will
eventually encounter a generalized boundary point of $X$ distinct from its
vertices.

###### Proof of Lemma 2.6.

Without loss of generality, position $T$ as in the hypotheses of Definition
2.10.

Since $\overline{\mathbf{v}^{1}\mathbf{v}^{2}}$ is the longest side of $T$, it
follows that $-v<v_{1}^{3}<v$ and

$T\left\backslash\,\left\\{\mathbf{v}^{1},\mathbf{v}^{2},\mathbf{v}^{3}\right\\}\right.\subset\bigcup_{t\geq-1}\operatorname{BD}\left(X,t\right).$
(2.1)

In other words, the bulldozers $\operatorname{BD}\left(X,t\right)$ can capture
all points in $T^{\prime}$. Since $T^{\prime}$ contains at least one point of
$X$, there exists a point $\mathbf{b}=\begin{pmatrix}b_{1}\\\
b_{2}\end{pmatrix}$ on the boundary of
$\operatorname{BD}\left(X,t_{\max}\right)$ that is not $\mathbf{v}^{1}$,
$\mathbf{v}^{2}$, or $\mathbf{v}^{3}$.

We claim that $\mathbf{b}$ is a generalized boundary point of $X$. Let

$t_{\max}\coloneqq\sup\left\\{t\geq-1\,\middle|\,\operatorname{BD}\left(X,t\right)\cap
X=\emptyset\right\\},$

which measures the position of the highest possible bulldozer
$\operatorname{BD}\left(X,t_{\max}\right)$ which does not intersect any points
of $X$. Consider the disk

$D\left(\varepsilon\right)\coloneqq\begin{pmatrix}b_{1}\\\
t_{\max}+\varepsilon\end{pmatrix}+B^{2}\subseteq\operatorname{BD}\left(X,\,t_{\max}+\varepsilon\right).$

For a small enough positive $\varepsilon$, this disk contains $\mathbf{b}$ but
does not intersect any other point of $X$. ∎

Figure 3: How to find the fourth generalized boundary point in the proof of
Theorem 2.6. The bulldozers are $\operatorname{BD}\left(X,-0.75\right)$
(medium orange) and $\operatorname{BD}\left(X,t_{\max}+\varepsilon\right)$
(light orange), with $t_{\max}=0.5$. The generalized boundary point
$\mathbf{b}=\begin{pmatrix}-0.25\\\
\hphantom{+}1.5\hphantom{0}\end{pmatrix}\in X^{\prime}$ is in dark purple and
the disk $D\left(\varepsilon\right)=\begin{pmatrix}-0.25\\\
0.5+\varepsilon\end{pmatrix}+B^{2}$ in dark orange. The grey arrows represent
the intuition of finding $\mathbf{b}$ by moving the bulldozer “upwards” until
it reaches a point of $X^{\prime}$.
The point $\mathbf{b}^{\prime}$ is on the boundary of
$\operatorname{BD}\left(X,t_{\max}\right)$, so it is also a generalized
boundary point of $X$ which we could have chosen instead of $\mathbf{b}$.

######  Remark 2.11.

The $y$-coordinate $b_{2}$ found in the above proof is usually equal to
$t_{\max}+1$. However, if $\mathbf{b}$ lies on the curved part of
$\operatorname{BD}\left(X,t_{\max}\right)$ then $t_{\max}<b_{2}<t_{\max}+1$.

######  Remark 2.12.

If $\mathbf{b}$ is just defined as a point of $X^{\prime}$ with smallest
$y$-coordinate, then it is not necessarily a generalized boundary point.
Figure 4(a) illustrates a scenario in which this point $\mathbf{b}$ lies very
close to $\mathbf{v}^{2}$, and the given disjoint cover of
$X^{\prime}\left\backslash\,\left\\{\mathbf{b}\right\\}\right.\\!$ cannot be
extended to an exact cover of $X$.

(a)

(b)

Figure 4: An example that illustrates the need for the complicated definition
of the bulldozer. The grey disks are an exact cover of
$X\left\backslash\,\left\\{\mathbf{b}\right\\}\right.$ while the orange disk
$D\left(\varepsilon\right)$ (see the proof of Lemma 2.6) is from the
bulldozer.
Left: The point $\mathbf{b}=\mathbf{y}$ has smallest $y$-coordinate among all
points in $X^{\prime}$. In this case, $\mathbf{b}$ cannot be covered by a disk
without $\mathbf{x}$ or $\mathbf{v}^{2}$ being covered by two disks. (The
faint brown disk at the top right shows that $\mathbf{b}$ cannot be covered in
this way by approaching from another edge of $T$.)
Right: The definition of the bulldozer fixes the problem in Figure 4(a). The
bulldozer finds a different point $\mathbf{b}=\mathbf{x}$, and this choice of
$\mathbf{b}$ results in a different disjoint cover $\mathscr{D}^{\prime}$ of
$X\left\backslash\,\left\\{\mathbf{b}\right\\}\right.\\!$.
If $\mathbf{b}$ is not covered by a disk in $\mathscr{D}^{\prime}$ then
$\mathscr{D}^{\prime}\cup\left\\{D\left(\varepsilon\right)\right\\}$ is an
exact cover of $X$.
If $\mathbf{b}$ is already covered by a disk in $\mathscr{D}^{\prime}$, as in
Figure 4(b), then $\mathscr{D}^{\prime}$ is an exact cover of $X$.

If all three sides of $T$ have lengths less than $2$, then
$\operatorname{BD}\left(X,t\right)=\emptyset$, so a different approach is
needed using the same idea. Let $\mathbf{h}$ be the orthocenter of $T$. For
each $1\leq i<j\leq 3$, let $D_{i,j}$ be the disk whose boundary passes
through $\mathbf{v}^{i}$, $\mathbf{v}^{j}$, and $\mathbf{h}$. The points
$\mathbf{v}^{1}$, $\mathbf{v}^{2}$, $\mathbf{v}^{3}$, and $\mathbf{h}$ form an
orthocentric system, and it is well known (e.g. [19], page 165) that the radii
of all the $D_{i,j}$ are equal to $R_{T}$. We only require $R_{T}>1$ for Lemma
2.7, but we also explain the other cases $R_{T}=1$ and $R_{T}<1$ below for
context.

For each $1\leq i<j\leq 3$, let $\operatorname{BD}_{i,j}$ be the unit disk
whose boundary passes through $\mathbf{v}^{i}$ and $\mathbf{v}^{j}$ and whose
center is on the same side of the line
$\overline{\mathbf{v}^{i}\mathbf{v}^{j}}$ as the center of $D_{i,j}$. For
convenience, we will also refer to the disks $\operatorname{BD}_{i,j}$ as
bulldozers—see Figure 5 for a comparison of $D_{i,j}$ and
$\operatorname{BD}_{i,j}$. We describe the relationship between $D_{i,j}$ and
$\operatorname{BD}_{i,j}$ for various values of $R_{T}$ below.

  1. 1.

If $R_{T}>1$, then $\operatorname{BD}_{i,j}$ is smaller than $D_{i,j}$ for all
$1\leq i<j\leq 3$. Then each $\operatorname{BD}_{i,j}$ can be pushed “further
into” $T$ than its corresponding $D_{i,j}$, in the sense that
$\operatorname{BD}_{i,j}\cap\,T\supset D_{i,j}\cap\,T$. Hence
$T^{\prime}\subseteq\operatorname{BD}_{1,2}\cup\operatorname{BD}_{1,3}\cup\operatorname{BD}_{2,3}$.
Each point of $X^{\prime}$ is contained in some bulldozer so there exists a
$\operatorname{BD}_{i^{\prime},j^{\prime}}$ whose intersection with
$X^{\prime}$ is nonempty. Then we keep the corresponding disk
$D_{i^{\prime},j^{\prime}}$, which contains at least one point of
$X^{\prime}$, while removing the other two disks. The desired fourth
generalized boundary point is contained in $D_{i^{\prime},j^{\prime}}$.

  2. 2.

If $R_{T}=1$, then $\operatorname{BD}_{i,j}=D_{i,j}$ for all $1\leq i<j\leq
3$. Then $\mathbf{h}$ is the only point of $T^{\prime}$ that is not covered by
the union $D_{1,2}\cup D_{1,3}\cup D_{2,3}$. However, $T$ can be covered by
four disks as stated in Lemma 2.8.

  3. 3.

If $R_{T}<1$, then the disks $\operatorname{BD}_{i,j}$ fail to cover some
neighborhood of $\mathbf{h}$. However, $T$ can be covered by a single disk as
stated in Lemma 2.9.

(a)

(b)

Figure 5: A comparison of $D_{i,j}$ and $\operatorname{BD}_{i,j}$. The unit
disks $D_{i,j}$ intersect at the orthocenter $\mathbf{h}$ and $T\subseteq
D_{1,2}\cup D_{1,3}\cup D_{2,3}$.
Left: If $R_{T}>1$ (in this case $\frac{8}{7}\approx 1.071$), then the
bulldozers are smaller than the unit disks and hence cover $T^{\prime}$ (Lemma
2.7), but a single unit disk (light blue) cannot cover $T^{\prime}$.
Right: If $R_{T}<1$ (in this case $\frac{45}{56}\approx 0.804$), then the
bulldozers are larger than the unit disks and cannot cover $T^{\prime}$, but
one unit disk (light blue) covers $T^{\prime}$.

We require the following technical geometric statements for the case
$R_{T}>1$.

######  Proposition 2.13.

Any right or obtuse triangle $T$ with longest side of length less than $2$ is
contained inside a unit disk.

###### Proof.

See Appendix B.1. ∎

######  Lemma 2.14.

Suppose that $T$ is an acute triangle with all side lengths less than $2$. If
$R_{T}>1$ then

$T^{\prime}=T\left\backslash\,\left\\{\mathbf{v}^{1},\mathbf{v}^{2},\mathbf{v}^{3}\right\\}\right.\\!\subseteq\operatorname{BD}_{1,2}\cup\operatorname{BD}_{1,3}\cup\operatorname{BD}_{2,3}.$

###### Proof.

See Appendix B.1. ∎

We now prove Lemma 2.7, in which $T$ has short sides but a large circumradius.

###### Proof of Lemma 2.7.

By Proposition 2.13, we may assume that $T$ is an acute triangle. By Lemma
2.14,

$T^{\prime}\subset\operatorname{BD}_{1,2}\cup\operatorname{BD}_{1,3}\cup\operatorname{BD}_{2,3}.$

Pick indices $i$ and $j$ such that the interior of
$\operatorname{BD}_{i,j}\left(X\right)$ contains at least one point
$\mathbf{b}\in X^{\prime}$. Without loss of generality, assume that $i=1$,
$j=2$, $\mathbf{v}^{1}=\begin{pmatrix}-v_{1}\\\
\hphantom{+}0_{\hphantom{1}}\end{pmatrix}$, and
$\mathbf{v}^{2}=\begin{pmatrix}v_{1}\\\ 0\end{pmatrix}$. Let

$t_{\max}^{\prime}\coloneqq\sup\left\\{t\geq-1\,\middle|\,\left(\begin{pmatrix}0\\\
t\end{pmatrix}+B^{2}\right)\cap X=\emptyset\right\\}.$

Let $\mathbf{b}$ be any point of $X^{\prime}$ on the boundary of
$\begin{pmatrix}0\\\ t_{\max}^{\prime}\end{pmatrix}+B^{2}$. This point is the
fourth generalized boundary point of $X$. ∎

###  2.2 A parameterized version of Inaba’s proof

Betke, Henk, and Wills (1994) [3] introduced the parametric density, a
variation of the packing density in which the disks are allowed to overlap,
during their work on a packing problem called the Sausage Conjecture [8]; see
[3, 5, 9] for further details. Let

$A_{2}\coloneqq\mathbb{Z}\begin{pmatrix}0\\\
2\end{pmatrix}+\mathbb{Z}\begin{pmatrix}\sqrt{3}\\\ 1\end{pmatrix}$

be the hexagonal lattice and
$\mathscr{A}_{2}^{\rho}\coloneqq\left\\{D_{\mathbf{c},\rho}\subset\mathbb{R}^{2}\,\middle|\,\mathbf{c}\in
A_{2}\right\\}$ be the collection of disks of radius $\rho\geq 1$ that are
centered at the points of $A_{2}$. This radius $\rho$ is called the parameter;
the case $\rho=1$ reduces to the usual hexagonal packing in Inaba’s proof and
we write $\mathscr{A}_{2}=\mathscr{A}_{2}^{1}$. We call the subset of
$\mathbb{R}^{2}$ covered by exactly one disk
$D_{\mathbf{c},\rho}\in\mathscr{A}_{2}^{\rho}$ the “good” region of
$\mathscr{A}_{2}^{\rho}$ and its complement the “bad” region. An exact cover
of $X$ requires each point in $X$ to avoid the “bad” region. If $\rho>1$, then
neighboring disks of $\mathscr{A}_{2}^{\rho}$ overlap (Figure 6), so the “bad”
region includes any part of the plane covered by multiple disks. The critical
value for $\rho$ minimizes the total area of the “bad” region and so maximizes
the lower bound for $\widehat{\sigma}_{2}$ (over all coverings of the form
$\mathscr{A}_{2}^{\rho}$).

Figure 6: The disks of $\mathscr{A}_{2}^{\rho}$ for $\rho=1$ (black) and
$\rho=1.07$ (blue).

We use the same argument as Inaba, but with the parameterized family
$\mathscr{A}_{2}^{\rho}$ of coverings, and combine it with the Extension
Argument for another proof of $\widehat{\sigma}_{2}\geq 16$. However,
$\mathscr{A}_{2}^{\rho}$ has another advantage over $\mathscr{A}_{2}$.
Removing one disk from $\mathscr{A}_{2}$ strictly expands the “bad” region, so
is never beneficial for exact covering. However, removing one disk
$D_{\mathbf{c},\rho}$ from $\mathscr{A}_{2}^{\rho}$ changes the subsets of
$D_{\mathbf{c}}$ which are covered by another disk from “bad” to “good.” Our
eventual proof of $\widehat{\sigma}_{2}\geq 17$ in the next subsection will
use similar methods to this proof.

Let $C$ be a packing set and $\rho\in\left(0,\infty\right)$. Our formulations
of disk covering have so far been restricted to unit disks, but $\rho B^{2}$
is not a unit disk for $\rho\neq 1$. However, covering an $X\in\mathscr{X}$ by
$\left\\{D_{\mathbf{c},\rho}\subset\mathbb{R}^{2}\,\middle|\,\mathbf{c}\in
C\right\\}$ is equivalent to covering $\frac{1}{\rho}X\in\mathscr{X}$ by
$\left\\{D_{\mathbf{c},1}\subset\mathbb{R}^{2}\,\middle|\,\mathbf{c}\in\frac{1}{\rho}C\right\\}$.
Hence an alternate intuition of the the parameterized family
$\mathscr{A}_{2}^{\rho}$ is keeping the disk radius at $1$ but pushing the
disks together by a factor of $\rho$.

If $\rho>1$, then the disks in $\mathscr{A}_{2}^{\rho}$ overlap, which
presents an additional complication when combining the parameterized extension
to Inaba’s proof with the generalized boundary point method in the previous
subsection. In the proofs of the Extension Argument and its generalization,
the (generalized) boundary points of $X$ were removed from $X$ before Inaba’s
probabilistic method was applied. When these (generalized) boundary points
were added back to $X$, each of them was covered by zero or one disk of
$\mathscr{A}_{2}^{\rho}$. However, it is possible for some (generalized)
boundary point to be covered by two disks of $\mathscr{A}_{2}^{\rho}$ and
neither disk can be removed without breaking the exact cover. To avoid this
problem, we make sure that each generalized boundary point avoids these
subsets of overlapping disks.

######  Definition 2.15.

Let $k\in\mathbb{N}$ and $\rho>0$. Define

$R_{k}^{\rho}\coloneqq\left\\{\mathbf{z}\in\mathbb{R}^{2}\,\middle|\,\mathbf{z}\text{
is in }k\text{ distinct disks of }\mathscr{A}_{2}^{\rho}\right\\}.$

If $\mathscr{A}_{2}^{\rho}$ is an exact cover of $X$, then $X$ must have the
following properties: $X\subset R_{1}^{\rho}$ and no points of $X$ may be in
$R_{0}^{\rho}$ or $R_{k}^{\rho}$ for all $k\geq 2$. A corresponding result
applies to any translate $\mathbf{t}+\mathscr{A}_{2}^{\rho}$, hence for
simplicity we write $R_{k}^{\rho}$ instead of $\mathbf{t}+R_{k}^{\rho}$ below.

We only require $\rho\in\left[1,\frac{2}{\sqrt{3}}\right]$ for the results in
this subsection. While $\rho$ can be any positive number, Inaba’s method
applied to $\mathscr{A}_{2}^{\rho}$ for other values of $\rho$ provide equal
or worse results:

  1. 1.

If $\rho<1$ then the empty space $R_{0}^{\rho}$ grows, so $\delta\left(\rho
B^{2},A_{2}\right)<\delta\left(B^{2},A_{2}\right)$.

  2. 2.

If $\rho>\frac{2}{\sqrt{3}}$ then $R_{0}^{\rho}=\emptyset$ and $R_{1}^{\rho}$
shrinks (and eventually becomes empty), a detrimental outcome compared to
$\rho=\frac{2}{\sqrt{3}}$.

For $\rho\in\left[1,\frac{2}{\sqrt{3}}\right]$ we have
$R_{k}^{\rho}=\emptyset$ for all $k\geq 3$, hence these sets can be ignored.

Since $A_{2}$ is a lattice, it suffices to limit our calculations to the
Voronoi region of $A_{2}$; see Section 3 below for the relevant definition.

######  Lemma 2.16.

Let $H\coloneqq\operatorname{VR}_{A_{2}}\left(\mathbf{0}\right)$ be the
Voronoi region of $\mathbf{0}\in A_{2}$. For all $k\in\mathbb{N}_{0}$ and
$\rho\in\left[1,\frac{2}{\sqrt{3}}\right]$, define

$f\left(\rho,k\right)\coloneqq\frac{\operatorname{area}\left(H\right)-k\operatorname{area}\left(R_{2}^{\rho}\cap
H\right)}{\operatorname{area}\left(R_{0}^{\rho}\cap
H\right)+\operatorname{area}\left(R_{2}^{\rho}\cap H\right)}+k.$ (2.2)

If $X\in\mathscr{X}^{\prime}$ has at most $\left\lceil
f\left(\rho,k\right)\right\rceil-1$ points, including at least $k$ generalized
boundary points, then $X$ can be exactly covered. (That is,
$\widehat{\sigma}_{2}\left(k\right)\geq\left\lceil
f\left(\rho,k\right)\right\rceil-1$.)

We comment on several special cases and examples of (2.2) below and in
(2.6)–(2.8).

  1. 1.

If $k=0$ then

$\displaystyle
f\left(\rho,0\right)=\frac{\operatorname{area}\left(H\right)}{\operatorname{area}\left(R_{0}^{\rho}\cap
H\right)+\operatorname{area}\left(R_{2}^{\rho}\cap H\right)}.$ (2.3)

This case is equivalent to not using the Generalized Extension Argument as we
do not treat the generalized boundary points differently from any other point
of $X$.

  2. 2.

If $\rho=1$ then

$\displaystyle f\left(1,k\right)$ $\displaystyle=$
$\displaystyle\frac{\operatorname{area}\left(H\right)}{\operatorname{area}\left(R_{0}^{1}\cap
H\right)}+k$ $\displaystyle=$
$\displaystyle\frac{1}{1-\delta\left(B^{2},A^{2}\right)}+k$ $\displaystyle=$
$\displaystyle 10.741...+k.$

This case is equivalent to only using (Part 1 of) the Generalized Extension
Argument as it ignores the parameterized family $\mathscr{A}_{2}^{\rho}$ for
all $\rho>1$.

  3. 3.

If $\rho=1$ and $k=0$ then we recover Inaba’s method:

$\displaystyle f\left(1,0\right)=10.741...\,.$ (2.5)

###### Proof.

Fix $\rho\in\left[1,\frac{2}{\sqrt{3}}\right]$. Suppose that
$X\in\mathscr{X}^{\prime}$ has $k$ generalized boundary points. We wish to
find a translation of $\mathscr{A}_{2}^{\rho}$ that meets the following
conditions:

  1. 1.

Each of the $k$ generalized boundary points $\mathbf{b}\in X$ is not in
$R_{2}^{\rho}$, so must be in $R_{0}^{\rho}$ or $R_{1}^{\rho}$.

Let $\mathscr{D}^{\prime\prime}$ be a disjoint cover of $X^{\prime\prime}$. We
cover the generalized boundary points in $R_{0}^{\rho}$ with a collection of
(possibly additional) disks as in the proof of the Generalized Extension
Argument 2.5. On the other hand, each generalized boundary point in
$R_{1}^{\rho}$ is already covered by a disk in $\mathscr{D}^{\prime\prime}$.

  2. 2.

Each of the $n-k$ remaining points $\mathbf{x}\in X$ is not in $R_{0}^{\rho}$
or $R_{2}^{\rho}$, so must be in $R_{1}^{\rho}$.

The sets of forbidden translation factors—see (A.1)—of $\mathbf{b}$ and
$\mathbf{x}$ as stated above are $-\mathbf{b}+R_{2}^{\rho}$ and
$-\mathbf{x}+\left(R_{2}^{\rho}\cup R_{2}^{\rho}\right)$ respectively.

If $n$ satisfies

$\operatorname{area}\left(H\right)>k\operatorname{area}\left(R_{2}^{\rho}\cap
H\right)+\left(n-k\right)\left(\operatorname{area}\left(R_{0}^{\rho}\cap
H\right)+\operatorname{area}\left(R_{2}^{\rho}\cap H\right)\right),$

then $\mathscr{A}_{2}^{\rho}$ can be translated to meet conditions 1 and 2.
Hence there is some exact cover $\mathscr{D}\supseteq\mathscr{A}_{2}^{\rho}$
of $X$. Solving the above inequality for $n$ yields

$n<\frac{\operatorname{area}\left(H\right)-k\operatorname{area}\left(R_{2}^{\rho}\cap
H\right)}{\operatorname{area}\left(R_{0}^{\rho}\cap
H\right)+\operatorname{area}\left(R_{2}^{\rho}\cap H\right)}+k.$

So $X$ can be exactly covered if $\left|X\right|\leq\left\lceil
f\left(\rho,k\right)\right\rceil-1$, cf. (A.2). ∎

###### Alternate proof of $\widehat{\sigma}_{2}\geq 16$.

Let $X\in\mathscr{X}^{\prime}$. We use elementary geometry to calculate the
areas mentioned in (2.2):

$\displaystyle\operatorname{area}\left(H\right)$ $\displaystyle=2\sqrt{3},$
$\displaystyle\operatorname{area}\left(R_{2}^{\rho}\cap H\right)$
$\displaystyle=6\left(\rho^{2}\operatorname{arcsec}\left(\rho\right)-\sqrt{\rho^{2}-1}\right),$
$\displaystyle\operatorname{area}\left(R_{0}^{\rho}\cap H\right)$
$\displaystyle=2\sqrt{3}-\pi\rho^{2}+\operatorname{area}\left(R_{2}^{\rho}\right).$

Since $\rho\in\left[1,\frac{2}{\sqrt{3}}\right]$ was picked arbitrarily, we
maximize $f\left(\rho,k\right)$ for each $k\in\mathbb{N}_{0}$. Let

$f_{\max}\left(k\right)\coloneqq\max_{\rho\in\left[1,\frac{2}{\sqrt{3}}\right]}f\left(\rho,k\right)\qquad\text{and}\qquad\rho_{\max}\left(k\right)\coloneqq\operatorname*{arg\,max}_{\rho\in\left[1,\frac{2}{\sqrt{3}}\right]}f\left(\rho,k\right)\text{.}$

By inspection (see Figure 7) and (2.3)–(2.5), we obtain

$\displaystyle f\left(1,0\right)$ $\displaystyle=10.741...\,,$ $\displaystyle
f_{\max}\left(0\right)$
$\displaystyle=13.928...\quad\text{at}\quad\rho_{\max}\left(0\right)=1.035...\,\text{,}$
(2.6) $\displaystyle f\left(1,3\right)$ $\displaystyle=13.741...\,,$
$\displaystyle f_{\max}\left(3\right)$
$\displaystyle=16.152...\quad\text{at}\quad\rho_{\max}\left(3\right)=1.028...\,\text{,}$
(2.7) $\displaystyle f\left(1,4\right)$ $\displaystyle=14.741...\,,$
$\displaystyle f_{\max}\left(4\right)$
$\displaystyle=16.948...\quad\text{at}\quad\rho_{\max}\left(4\right)=1.026...\,\text{,}$
(2.8) $\displaystyle f\left(1,5\right)$ $\displaystyle=15.741...\,,$
$\displaystyle f_{\max}\left(5\right)$
$\displaystyle=17.766...\quad\text{at}\quad\rho_{\max}\left(5\right)=1.024...\,\text{.}$
(2.9)

The lower bound of $\widehat{\sigma}_{2}\geq 16$ follows from (2.8), Lemma
2.16, and the Generalized Extension Argument 2.5. ∎

Figure 7: The graphs of $y=f\left(\rho,k\right)$ for
$\rho=x\in\left[1,\frac{2}{\sqrt{3}}\right]$ ($x$-axis) and $k=0$ (light
yellow), $k=3$ (green), $k=4$ (teal), and $k=5$ (dark purple).

######  Remark 2.17.

Unlike the proof of $\widehat{\sigma}_{2}\geq 16$ in the previous section, we
did not use Aloupis, Hearn, Iwasawa, and Uehara’s result of $\sigma_{2}\geq
12$ in this proof. Their proof used specific technical arguments on subsets of
vertical lines in $\mathbb{R}^{2}$, which we were unable to beneficially adapt
to the parametric context.

The benefit of the parameterized family $\mathscr{A}_{2}^{\rho}$ compared to
the usual “nonparametric” hexagonal lattice $\mathscr{A}_{2}$ is cut-and-dry:
The $\rho_{\max}>1$ case is always better than or equal to the $\rho=1$ case.
For each $k\in\mathbb{N}_{0}$, we have $f_{\max}\left(k\right)\geq
f\left(1,k\right)$ by definition of $f_{\max}$. However, as a consequence of
$\left.\frac{\partial}{\partial\rho}f\left(\rho,k\right)\right|_{\rho=1}>0$,
we also have $f_{\max}\left(k\right)>f\left(1,k\right)$. This inequality and
its counterpart
$\left.\frac{\partial}{\partial\rho}f\left(\rho,k\right)\right|_{\rho=\frac{2}{\sqrt{3}}}<0$
are intuitively justified by comparing
$\operatorname{area}\left(R_{0}^{\rho}\right)$ and
$\operatorname{area}\left(R_{2}^{\rho}\right)$ for $\rho=1$ and
$1+\varepsilon$, and $\rho=\frac{2}{\sqrt{3}}$ and
$\frac{2}{\sqrt{3}}-\varepsilon$ respectively.

On the other hand, the function $f$ is not strong enough to prove the result
$\widehat{\sigma}_{2}\geq 12+k$ for all $k\in\mathbb{N}$. Below we compare the
two methods that obtain $\widehat{\sigma}_{2}\geq 16$:

  1. 1.

The combination of Aloupis, Hearn, Iwasawa, and Uehara’s [1] lower bound and
Part 1 of the Generalized Extension Argument 2.5:

$\widehat{\sigma}_{2}\left(k\right)\geq 12+k$ (2.10)

  2. 2.

The combination of Inaba’s original lower bound (Theorem A.1), Part 1 of the
Generalized Extension Argument 2.5, and the parameterized version of Inaba’s
proof (Lemma 2.16):

$\widehat{\sigma}_{2}\left(k\right)\geq\left\lceil
f_{\max}\left(k\right)\right\rceil-1=\begin{cases}13+k&\hphantom{0}0\leq k\leq
3,\\\ 12+k&\hphantom{0}4\leq k\leq 11,\\\ 11+k&12\leq k\leq 45,\\\ 10+k&46\leq
k.\end{cases}$ (2.11)

As shown222 An explicit formulation of the local maximum point
$\rho_{\max}\left(k\right)$ seems to be difficult. The equation
$\frac{\partial}{\partial\rho}f\left(\rho,k\right)=0$ which
$\rho_{\max}\left(k\right)$ satisfies is equivalent (for our purposes) to
$6\left(k+2\right)\operatorname{arcsec}\left(\rho\right)-\sqrt{3}\pi
k\sqrt{\rho^{2}-1}-\pi=0.$ (2.12) Note that
$\operatorname{arcsec}\left(\rho\right)=\sqrt{\rho^{2}-1}$ at $\rho=1$ and
$\frac{d}{d\rho}\left(\sqrt{\rho^{2}-1}-\operatorname{arcsec}\left(\rho\right)\right)=\sqrt{1-\frac{1}{\rho^{2}}}$
is small for $\rho\approx 1$. We substitute
$\operatorname{arcsec}\left(\rho\right)$ for $\sqrt{\rho^{2}-1}$ in (2.12) so
it becomes a linear polynomial in $\operatorname{arcsec}\left(\rho\right)$.
The relevant solution is
$\rho=\widetilde{\rho}_{\max}\left(k\right)\coloneqq\sec\left(\frac{\pi}{6k+12-\sqrt{3}\pi
k}\right)$, which is near $\rho_{\max}\left(k\right)$. In Figure 8, we use
$f\left(\widetilde{\rho}_{\max}\left(k\right),k\right)$ instead of
$f_{\max}\left(k\right)$.  in Figure 8, for $k\geq 12$, the Generalized
Extension Argument obtains a better bound for $\widehat{\sigma}_{2}$ than
Lemma 2.16, while for $k\leq 3$ the opposite holds. However, by Part 2 of the
Generalized Extension Argument, we may assume that $k\geq 4$. Hence the first
result is actually stronger than the second in practice. Eventually the
parameter does not deliver any benefit—Inaba with the generalized boundary
points already achieves $\widehat{\sigma}_{2}\left(k\right)\geq 10+k$, as
shown in (2.5).

Figure 8: A comparison of close approximations to $y=f_{\max}\left(k\right)-k$
(light blue) and $y=\left(\left\lceil
f_{\max}\left(k\right)\right\rceil-1\right)-k$ (dark blue) with
$y=\left(12+k\right)-k$ (green), where $k=x$.

######  Remark 2.18.

We conjecture that the improvement that $f_{\max}\left(k\right)$ brings to the
table over $f_{\max}\left(0\right)$ is strictly “subadditive” in the following
sense. Let $g\left(\rho,k\right)\coloneqq
f\left(\rho,k\right)-f\left(\rho,0\right)$ and
$g_{\max}\left(k\right)\coloneqq
f_{\max}\left(k\right)-f_{\max}\left(0\right)$. For all $k_{1},k_{2}\geq 0$,
we have (with the corresponding equalities for $g$ and $f$ listed as a
comparison)

$\displaystyle g\left(1,k_{1}+k_{2}\right)$
$\displaystyle=g\left(1,k_{1}\right)+g\left(1,k_{2}\right),$ $\displaystyle
g_{\max}\left(k_{1}+k_{2}\right)$
$\displaystyle<g_{\max}\left(k_{1}\right)+g_{\max}\left(k_{2}\right),$

and alternatively

$\displaystyle f\left(1,k_{1}+k_{2}\right)$
$\displaystyle=f\left(1,k_{1}\right)+k_{2},$ $\displaystyle
f_{\max}\left(k_{1}+k_{2}\right)$
$\displaystyle<f_{\max}\left(k_{1}\right)+k_{2}.$ (2.13)

If we show that every $X\in\mathscr{X}^{\prime}$ has at least $4+k$
generalized boundary points for some $k>0$, then
$\widehat{\sigma}_{2}\geq\left\lceil f_{\max}\left(4+k\right)\right\rceil-1$
by Lemma 2.16. However, the subadditivity of (2.13) implies that adding the
$k$ additional boundary points will improve the lower bound for
$\widehat{\sigma}_{2}$ by less than or equal to $k$. The reason is the
overlapping disks when $\rho>1$. When we performed our calculations with
$\mathscr{A}_{2}^{\rho}$ in the proof of Lemma 2.16, we had to exclude the
(generalized) boundary points from $R_{2}^{\rho}$, so they could no longer be
added back “for free.”

###  2.3 A redundant disk

Suppose that $X\in\mathscr{X}$ has a triangular or quadrilateral convex hull,
$\mathbf{v}^{1}\in X$ is a boundary point that is covered by two disks of
$\mathscr{A}_{2}^{\rho}$, and $\mathscr{A}_{2}^{\rho}$ is an exact cover of
$X\left\backslash\,\left\\{\mathbf{v}^{1}\right\\}\right.$. Under certain
conditions, we can remove one of the disks $D$ that covers $\mathbf{v}^{1}$
without breaking the exact cover. In other words, although
$\mathscr{A}_{2}^{\rho}$ is not an exact cover of $X$, we show that
$\mathscr{A}_{2}^{\rho}\left\backslash\,\left\\{D\right\\}\right.$ is an exact
cover of $X$. Hence we may call $D$ a “redundant disk.” This method offers a
slight benefit:

######  Definition 2.19.

Define the following subsets of $\mathbb{R}^{2}$ as follows (see Figure 9(a)):

  1. 1.

Let $R_{2,1}^{\rho}$ be the set of points in $\mathbb{R}^{2}$ which are
contained in the intersection of two disks centered at different
$x$-coordinates.

  2. 2.

Let $R_{2,2}^{\rho}$ be the set of points in $\mathbb{R}^{2}$ which are
contained in the intersection of two disks centered at the same
$x$-coordinate.

  3. 3.

For any distinct $\mathbf{y},\mathbf{z}\in A_{2}$, let
$R^{\rho}\left(\mathbf{y},\mathbf{z}\right)\coloneqq\rho
D_{\mathbf{y}}\cap\rho D_{\mathbf{z}}$.

(a)

(b)

Figure 9: A demonstration of the redundant disk method (Proposition 2.22). The
collection $\mathscr{A}_{2}^{\rho}$ (light grey disks) for
$\rho=\frac{8}{7}\approx 1.067$; the subsets $R_{2,1}^{\rho}$ and
$R_{2,2}^{\rho}$ are light green and dark grey respectively. The set
$T^{\prime}$ is indicated by the dark green triangle. The blue disk is an
extra disk necessary for the exact covering of $X$.
Left: The set $R_{2,1}^{\rho}$ contains a vertex with small angle less than
$\frac{\pi}{2}$.
Right: A disk can be removed from $\mathscr{A}_{2}^{\rho}$ without breaking
the exact cover (see Proposition 2.22).

Note that
$R_{2}^{\rho}=\bigcup_{\mathbf{y}\neq\mathbf{z}}R^{\rho}\left(\mathbf{y},\mathbf{z}\right)$
and each point of $R_{2}^{\rho}$ is contained in either $R_{2,1}^{\rho}$ or
$R_{2,2}^{\rho}$.

Suppose that $X$ is exactly covered by $\mathscr{A}_{2}^{\rho}$ (or any
covering of radius-$\rho$ disks that contains $\mathscr{A}_{2}^{\rho}$).
Without loss of generality, assume that $\mathbf{v}^{1}\in
R^{\rho}\left(\mathbf{y},\mathbf{z}\right)\subset R_{2,1}^{\rho}$,
$\mathbf{y}$ is to the left of $\mathbf{z}$, and
$X\left\backslash\,\left\\{\mathbf{v}^{1}\right\\}\right.$ is to the right of
$\mathbf{y}$, as shown in Figure 9(a). If $\operatorname{conv}X$ is “pointy”
enough at $\mathbf{v}^{1}$, then the “roundness” of the disk $D_{\mathbf{z}}$
ensures that $D_{\mathbf{z}}$ covers all nearby areas of
$\operatorname{conv}X$ without any help from additional disks. In particular,
$D_{\mathbf{y}}$ can be removed from the packing $\mathscr{A}_{2}^{\rho}$
without breaking the exact cover, even though
$D_{\mathbf{y}}\cap\operatorname{conv}X\neq\emptyset$ (Figure 9(b)). Then the
subset $R_{2,1}^{\rho}$ can be ignored and treated as part of $R_{1}^{\rho}$
from the perspective of $\mathbf{v}^{1}$, resulting in a slightly better (or
equal) lower bound for $\widehat{\sigma}_{2}$ (Lemma 2.23).

We carefully analyze the geometry of $R_{2,1}^{\rho}$ and $R_{2,2}^{\rho}$ to
formalize the above intuition.

######  Remark 2.20.

Figures 10(a) and 10(b) show that unlike $R_{2,1}^{\rho}$, the set
$R_{2,2}^{\rho}$ lacks redundancy. If $\mathbf{v}^{1}\in R_{2,2}^{\rho}$ then
in general, no disk that covers $X$ can be removed without breaking the exact
cover.

(a)

(b)

Figure 10: If $\mathbf{v}^{1}\in R_{2,2}^{\rho}$, then a disk cannot
necessarily be removed from $\mathscr{A}_{2}^{\rho}$ without breaking the
exact covering, as shown by the point in Figure 10(b) marked by an arrow.

######  Proposition 2.21.

Let $\rho\in\left[1,\sqrt{6}-\sqrt{2}\approx 1.0353\right]$. Let
$\mathbf{y},\mathbf{z}\in A_{2}$ with $y_{1}<z_{1}$, and
$\mathbf{w}\in\operatorname{bd}\left(R^{\rho}\left(\mathbf{y},\mathbf{z}\right)\right)$.
The slope of the tangent line $L^{\rho}\left(\mathbf{w}\right)$ to
$R^{\rho}\left(\mathbf{y},\mathbf{z}\right)$ at $\mathbf{w}$ has absolute
value greater than or equal to $1$.

###### Proof.

See Appendix B.2. ∎

######  Proposition 2.22.

Let $X\in\mathscr{X}$ and $\rho\in\left[1,\sqrt{6}-\sqrt{2}\right]$. Suppose
that $X$ meets the following conditions (Figure 9(a)):

  1. 1.

There exist $\mathbf{v}^{2},\mathbf{v}^{1},\mathbf{v}^{3}\in X$ such that the
interior angle
$\angle\mathbf{v}^{2}\mathbf{v}^{1}\mathbf{v}^{3}\leq\frac{\pi}{2}$.

  2. 2.

The slopes of $\overline{\mathbf{v}^{1}\mathbf{v}^{2}}$ and
$\overline{\mathbf{v}^{1}\mathbf{v}^{3}}$ have equal magnitude and opposite
signs.

  3. 3.

Every point of $X\left\backslash\,\left\\{\mathbf{v}^{1}\right\\}\right.$ is
to the right of $\mathbf{v}^{1}$.

  4. 4.

The small angle point $\mathbf{v}^{1}$ is contained in some
$R^{\rho}\left(\mathbf{y},\mathbf{z}\right)\subset R_{2,1}^{\rho}$,
$y_{1}<z_{1}$.

If $X$ is exactly covered by $\mathscr{A}_{2}^{\rho}$ (or any covering of
radius-$\rho$ disks that contains $\mathscr{A}_{2}^{\rho}$), then $X$ is also
exactly covered by
$\left.\mathscr{A}_{2}^{\rho}\,\right\backslash\left\\{D_{\mathbf{y}}\right\\}$
(Figure 9(b)).

###### Proof.

See Appendix B.2. ∎

######  Lemma 2.23.

Let $X\in\mathscr{X}^{\prime}$ with $\lvert X\rvert\leq 17$. If
$\operatorname{conv}X$ is a triangle or a quadrilateral, then $X$ can be
exactly covered.

###### Proof.

Since $\operatorname{conv}X$ has three or four sides, at least one vertex
(after relabeling) has interior angle
$\angle\mathbf{v}^{2}\mathbf{v}^{1}\mathbf{v}^{3}\leq\frac{\pi}{2}$. Without
loss of generality, we may flip and rotate $X$ such that the hypotheses 1–3 of
Proposition 2.22 are satisfied.

Suppose that $\mathbf{v}^{1}\in
R^{\rho}\left(\mathbf{y},\mathbf{z}\right)\subset R_{2,1}^{\rho}$ (hypothesis
4). This point is covered by two disks $B_{\mathbf{y}}$ and $B_{\mathbf{z}}$
of $\mathscr{A}_{2}^{\rho}$. However, the conclusion of Proposition 2.22
states that $X$ is exactly covered by the smaller covering
$\left.\mathscr{A}_{2}^{\rho}\,\right\backslash\left\\{D_{\mathbf{y}}\right\\}$.

Now suppose that $\mathbf{v}^{1}\notin R_{2,1}^{\rho}$. This case reduces to
the case of a generalized boundary point in the proof of Lemma 2.16.

Let $H=\operatorname{VR}_{A_{2}}\left(\mathbf{0}\right)$. The following
exclusions apply (cf. the proof of Lemma 2.16):

  1. 1.

The small angle point $\mathbf{v}^{1}\in X$ cannot be in $R_{2,2}^{\rho}$, so
is in $R_{0}^{\rho}$, $R_{1}^{\rho}$, or $R_{2,1}^{\rho}$.

  2. 2.

Three (or more) additional generalized boundary points
$\mathbf{v}^{2},\mathbf{v}^{3},\mathbf{b}^{4}$ of $X$ exist by Lemmas 2.6 and
2.7 (including the two other vertices mentioned above). Each of these points
cannot be in $R_{2}^{\rho}=R_{2,1}^{\rho}\cup R_{2,2}^{\rho}$, so is in
$R_{0}^{\rho}$ or $R_{1}^{\rho}$.

  3. 3.

Each of the $n-4$ remaining points of $X$ cannot be in $R_{0}^{\rho}$ or
$R_{2}^{\rho}$, so is in $R_{1}^{\rho}$.

The sets of forbidden translation vectors are
$-\mathbf{v}^{1}+R_{2,2}^{\rho}$; $-\mathbf{v}^{2}+R_{2}^{\rho}$,
$-\mathbf{v}^{3}+R_{2}^{\rho}$, and $-\mathbf{b}^{4}+R_{2}^{\rho}$; and
$-\mathbf{x}+\left(R_{0}^{\rho}\cup R_{2}^{\rho}\right)$ for $\mathbf{x}\in
X\left\backslash\,\left\\{\mathbf{v}^{1},\mathbf{v}^{2},\mathbf{v}^{3},\mathbf{b}^{4}\right\\}\right.$
respectively.

So if $n$ satisfies

$\operatorname{area}\left(H\right)>\operatorname{area}\left(R_{2,2}^{\rho}\cap
H\right)+3\operatorname{area}\left(R_{2}^{\rho}\cap
H\right)+\left(n-4\right)\left(\operatorname{area}\left(R_{0}^{\rho}\cap
H\right)+\operatorname{area}\left(R_{2}^{\rho}\cap H\right)\right),$

then $\mathscr{A}_{2}^{\rho}$ can be translated to meet conditions 1, 2, and
3, and so there is an exact cover $\mathscr{D}$ of $X$. Accordingly, for
$\rho\in\left[1,\sqrt{6}-\sqrt{2}\right]$ define

$f_{\text{r}}\left(\rho\right)\coloneqq\frac{\operatorname{area}\left(H\right)-3\operatorname{area}\left(R_{2}^{\rho}\cap
H\right)-\frac{1}{3}\operatorname{area}\left(R_{2,2}^{\rho}\cap
H\right)}{\operatorname{area}\left(R_{0}^{\rho}\cap
H\right)+\operatorname{area}\left(R_{2}^{\rho}\cap H\right)}+4.$

If $\left|X\right|\leq\left\lceil f_{\text{r}}\left(\rho\right)\right\rceil-1$
points then $X$ can be exactly covered by $\mathscr{D}$. This cover contains
all disks of $\mathscr{A}_{2}^{\rho}$ except for possibly one redundant disk.

For any $\mathbf{x}\in A_{2}$, the disk $D_{\mathbf{x}}$ contains four
distinct intersections

$R^{\rho}\left(\begin{pmatrix}x_{1}\\\
x_{2}\end{pmatrix},\begin{pmatrix}x_{1}\pm\sqrt{3}\\\ x_{2}\pm
1\end{pmatrix}\right)\subset R_{1,2}$

and two distinct intersections

$R^{\rho}\left(\begin{pmatrix}x_{1}\\\
x_{2}\end{pmatrix},\begin{pmatrix}x_{1}\\\ x_{2}\pm
2\end{pmatrix}\right)\subset R_{2,2}^{\rho},$

all of identical area. Hence $\operatorname{area}\left(R_{2,2}^{\rho}\cap
H\right)=\frac{1}{3}\operatorname{area}\left(R_{2}^{\rho}\cap H\right)$. Using
the area calculations from the proof of Lemma 2.16 and inspection, we obtain

$\max_{\rho\in\left[1,\frac{2}{\sqrt{3}}\right]}f_{\text{r}}\left(\rho\right)=17.082...\quad\text{at}\quad\rho=1.027...\,\text{.}\qed$

Finally, we prove our lower bound of $\widehat{\sigma}_{2}\geq 17$.

###### Proof of Theorem 1.2.

Let $X\in\mathscr{X}^{\prime}$ with $\lvert X\rvert\leq 17$.

  1. 1.

If $\operatorname{conv}X$ has three or four sides, then $X$ can be exactly
covered by Lemma 2.23.

  2. 2.

If $\operatorname{conv}X$ has five or more sides, then $X$ has at least five
generalized boundary points, so $X$ can be exactly covered by the inequality
$\widehat{\sigma}_{2}\left(5\right)\geq 17$ from either of the lower bounds
2.10 or 2.11.

∎

##  3 An upper bound

######  Definition 3.1.

Let $X\subset\mathbb{R}^{2}$ be a non-empty set. The distance of a point
$\mathbf{y}\in\mathbb{R}^{2}$ to $X$ is defined by

$\operatorname*{dist}\left(\mathbf{y},X\right)\coloneqq\inf\\{\|\mathbf{y}-\mathbf{x}\|\mid\mathbf{x}\in
X\\}$ (3.1)

and the $\varepsilon$-extension of $X$ is given by

$X_{\varepsilon}\coloneqq\left\\{\mathbf{y}\in\mathbb{R}^{2}\mid\operatorname*{dist}\left(\mathbf{y},X\right)\leq\varepsilon\right\\}.$
(3.2)

We say that $X$ is an $\varepsilon$-net of $M\subset\mathbb{R}^{2}$ if
$M\subset X_{\varepsilon}$.

######  Definition 3.2.

Let $M\subset\mathbb{R}^{2}$ and $\varepsilon>0$. We say that $M$ is an
$\varepsilon$-blocker if every $\varepsilon$-net $X\in\mathscr{X}$ of $M$ does
not have an exact cover.

We recall that the covering number $N\left(M,\varepsilon\right)$ of a set
$M\subset\mathbb{R}^{2}$ is the minimal cardinality of an $\varepsilon$-net of
$M$. The following statement is a direct consequence of Definition 3.2.

######  Proposition 3.3.

Let $M\subset\mathbb{R}^{2}$ be an $\varepsilon$-blocker. Then
$\widehat{\sigma}_{2}<N\left(M,\varepsilon\right)$. ∎

Our upper bound on $\widehat{\sigma}_{2}$ follows from the following result,
which asserts that every open disk of radius $R>1$ is an $\varepsilon$-blocker
for a suitably chosen $\varepsilon>0$.

######  Proposition 3.4.

Let $\varepsilon\in\left(0,7-\sqrt{48}\approx 0.0718\right]$ and

$R\geq\frac{3}{2}\left(1+\varepsilon\right)-\frac{1}{2}\sqrt{1-14\varepsilon+\varepsilon^{2}}.$
(3.3)

Then $D_{\mathbf{0},R}$ is an $\varepsilon$-blocker.

The proof of Proposition 3.4 is based on properties of Voronoi diagrams. For
the following definition and an overview of Voronoi diagrams, we refer to [13,
Ch. 6].

######  Definition 3.5.

Let $P\in\mathscr{X}$. The Voronoi region of $p\in P$ is given by

$\operatorname{VR}_{P}(\mathbf{p})\coloneqq\left\\{\mathbf{x}\in\mathbb{R}^{2}\,\middle|\,\|\mathbf{x}-\mathbf{p}\|\leq\|\mathbf{x}-\mathbf{q}\|\text{
for all }\mathbf{q}\in P\right\\}.$ (3.4)

It can be shown that every Voronoi region is a polyhedron and that the
intersection of two Voronoi regions is a face of both. Therefore, the set of
Voronoi regions

$\left\\{\operatorname{VR}_{P}(\mathbf{p})\subset\mathbb{R}^{2}\,\middle|\,\mathbf{p}\in
P\right\\}$ (3.5)

forms the set of maximal cells of a polyhedral complex, which is called the
Voronoi diagram of $P$ and is denoted by $\operatorname{VD}_{P}$.

We say that a set $P\in\mathscr{X}$ induces an exact cover of
$X\in\mathscr{X}$ if $\mathscr{D}_{P}$ is an exact cover of $X$. The following
Lemma asserts that a set $P\in\mathscr{X}$ that induces an exact cover of
$X\in\mathscr{X}$ has “almost spherical” Voronoi regions in the
$\varepsilon$-extension of $X$.

######  Lemma 3.6.

Let $\varepsilon\in(0,1)$. If $P\in\mathscr{X}$ induces an exact cover of
$X\in\mathscr{X}$, then for every $\mathbf{p}\in P$ we have

$\left(D_{\mathbf{p},1-\varepsilon}\cap
X_{\varepsilon}\right)\subset\left(\operatorname{VR}_{P}(\mathbf{p})\cap
X_{\varepsilon}\right)\subset D_{\mathbf{p},1+\varepsilon}.$ (3.6)

###### Proof.

Let $\mathbf{y}\in D_{\mathbf{p},1-\varepsilon}\cap X_{\varepsilon}$. By
definition of $X_{\varepsilon}$, there exists a point $\mathbf{x}\in X$ with
$\|\mathbf{x}-\mathbf{y}\|\leq\varepsilon$. Since $\mathbf{y}\in
D_{\mathbf{p},1-\varepsilon}$, we have $\mathbf{x}\in D_{\mathbf{p}}$. Let
$\mathbf{q}\in P$ with $\mathbf{y}\in\operatorname{VR}_{P}(\mathbf{q})$.
Because $\|\mathbf{y}-\mathbf{q}\|\leq\|\mathbf{y}-\mathbf{p}\|$ and
$\mathbf{y}\in D_{\mathbf{p},1-\varepsilon}$, we also have $\mathbf{x}\in
D_{\mathbf{q}}$. Using the fact that $\mathscr{D}_{P}$ is an exact cover of
$X$, it follows that $\mathbf{p}=\mathbf{q}$.

Now let $\mathbf{y}\in\operatorname{VR}_{P}(\mathbf{p})\cap X_{\varepsilon}$.
Again, there is an $\mathbf{x}\in X$ with
$\|\mathbf{x}-\mathbf{y}\|\leq\varepsilon$. Because $\mathscr{D}_{P}$ is an
exact cover of $X$, there exists a $\mathbf{q}\in P$ with $\mathbf{x}\in
D_{\mathbf{q}}$ and hence we have

$1>\|\mathbf{x}-\mathbf{q}\|\geq\|\mathbf{q}-\mathbf{y}\|-\|\mathbf{x}-\mathbf{y}\|\geq\|\mathbf{p}-\mathbf{y}\|-\varepsilon.\qed$

The basic idea of our proof is that three “almost spherical” Voronoi regions
cannot meet in a vertex $\mathbf{v}$ of $\operatorname{VD}_{P}$. The following
Lemma establishes the existence of such a vertex.

######  Lemma 3.7.

Let $\varepsilon\in\left(0,\frac{1}{3}\right)$ and $X\in\mathscr{X}$ be an
$\varepsilon$-net of $D_{\mathbf{0},1+\varepsilon}$. If $P\in\mathscr{X}$
induces an exact cover of $X$, then $\operatorname{VD}_{P}$ has a vertex
$\mathbf{v}\in D_{\mathbf{0},1+\varepsilon}$.

###### Proof.

Because $X$ is an $\varepsilon$-net of $D_{\mathbf{0},1+\varepsilon}$, there
exists a point $\mathbf{x}\in X\cap D_{\mathbf{0},\varepsilon}$. Moreover,
since $\mathscr{D}_{P}$ is an exact cover of $X$, there exists a
$\mathbf{p}\in P$ with $\mathbf{x}\in D_{\mathbf{p}}$ and hence $\mathbf{p}\in
D_{\mathbf{0},1+\varepsilon}$. Let $L\subset\mathbb{R}^{2}$ be the
perpendicular bisector of $\mathbf{p}$ and $\mathbf{0}$. Then the set
$L\cap\operatorname{bd}D_{\mathbf{0},1+\varepsilon}$ contains exactly two
points $\mathbf{y}_{1},\mathbf{y}_{2}$, both of which have distance
$1+\varepsilon$ to $\mathbf{p}$ (see Figure 11). Let $A$ be the circular arc
of $\operatorname{bd}D_{\mathbf{0},1+\varepsilon}$ that goes from
$\mathbf{y}_{1}$ to $\mathbf{y}_{2}$ and is on the opposite site of
$\mathbf{p}$. All points in $A$ have distance at least $1+\varepsilon$ to
$\mathbf{p}$. By Lemma 3.6, we have
$A\subset\mathbb{R}^{2}\setminus\operatorname{VR}_{P}(\mathbf{p})$. If
$\operatorname{VD}_{P}$ has no vertex in $D_{\mathbf{0},1+\varepsilon}$, then
the line segment $\operatorname{conv}\\{\mathbf{y}_{1},\mathbf{y}_{2}\\}$ is
contained in $\mathbb{R}^{2}\setminus\operatorname{VR}_{P}(\mathbf{p})$. In
particular, the point $\frac{\mathbf{y}_{1}+\mathbf{y}_{2}}{2}\in
X_{\varepsilon}$ is contained in
$\mathbb{R}^{2}\setminus\operatorname{VR}_{P}(\mathbf{p})$. Then, by Lemma
3.6, we get $\frac{\mathbf{y}_{1}+\mathbf{y}_{2}}{2}\notin
D_{\mathbf{p},1-\varepsilon}$. But this is a contradiction to

$\left\|\mathbf{p}-\frac{\mathbf{y}_{1}+\mathbf{y}_{2}}{2}\right\|=\frac{1}{2}\|\mathbf{p}-\mathbf{0}\|<\frac{1+\varepsilon}{2}<\frac{2}{3}<1-\varepsilon.\qed$

Figure 11: Since $A$ and $\operatorname{VR}_{P}(\mathbf{p})$ are disjoint,
$\operatorname{VR}_{P}$ either has a vertex in $D_{\mathbf{0},1+\varepsilon}$
or it does not contain the midpoint of $\mathbf{0}$ and $\mathbf{p}$, leading
to a contradiction to Lemma 3.6.

###### Proof of Proposition 3.4.

Let $X\in\mathscr{X}$ be an $\varepsilon$-net of $D_{\mathbf{0},R}$. We assume
towards a contradiction that there exists an exact cover $\mathscr{D}_{P}$ of
$X$. Because $R>1+\varepsilon$, $X$ is also an $\varepsilon$-net of
$D_{\mathbf{0},1+\varepsilon}$. By Lemma 3.7, $\operatorname{VD}_{P}$ has a
vertex $\mathbf{v}\in D_{\mathbf{0},1+\varepsilon}$, so there are three
distinct points $\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{p}_{3}\in P$ with

$\mathbf{v}\in\textstyle\operatorname{VR}_{P}(\mathbf{p}_{1})\cap\operatorname{VR}_{P}(\mathbf{p}_{2})\cap\operatorname{VR}_{P}(\mathbf{p}_{3}).$
(3.7)

By Lemma 3.6, we have

$1+\varepsilon>\|\mathbf{v}-\mathbf{p}_{1}\|=\|\mathbf{v}-\mathbf{p}_{2}\|=\|\mathbf{v}-\mathbf{p}_{3}\|.$
(3.8)

Without loss of generality, we assume that the smaller angle between the
vectors $\mathbf{p}_{1}-\mathbf{v}$ and $\mathbf{p}_{2}-\mathbf{v}$ is at most
$\frac{2\pi}{3}$ (see Figure 12). Because $\varepsilon\leq 7-\sqrt{48}$, we
have $1-14\varepsilon+\varepsilon^{2}\geq 0$ and hence we can set

$\mathbf{y}\coloneqq\mathbf{v}+\left(\frac{1+\varepsilon}{2}-\frac{1}{2}\sqrt{1-14\varepsilon+\varepsilon^{2}}\right)\frac{\frac{\mathbf{p}_{1}+\mathbf{p}_{2}}{2}-\mathbf{v}}{\left\|\frac{\mathbf{p}_{1}+\mathbf{p}_{2}}{2}-\mathbf{v}\right\|}.$
(3.9)

Figure 12: The point $\mathbf{y}$ is contained in
$D_{\mathbf{p}_{1},1-\varepsilon}\cap D_{\mathbf{p}_{2},1-\varepsilon}\cap
D_{\mathbf{0},R}$, which leads to a contradiction to Lemma 3.6.

Let $i\in\\{1,2\\}$. We denote the smaller angle between the vectors
$\mathbf{p}_{i}-\mathbf{v}$ and $\mathbf{y}-\mathbf{v}$ by $\theta$. By the
law of cosines, we have

$\|\mathbf{y}-\mathbf{p}_{i}\|^{2}=\|\mathbf{v}-\mathbf{p}_{i}\|^{2}+\|\mathbf{y}-\mathbf{v}\|^{2}-2\cdot\|\mathbf{v}-\mathbf{p}_{i}\|\cdot\|\mathbf{y}-\mathbf{v}\|\cdot\cos(\theta).$
(3.10)

Since $\theta\in\left[0,\frac{\pi}{3}\right]$, we have
$\cos(\theta)\geq\frac{1}{2}$. Using (3.8) and the fact that
$\|\mathbf{v}-\mathbf{p}_{i}\|\geq\|\mathbf{y}-\mathbf{v}\|$, we obtain

$\displaystyle\|\mathbf{y}-\mathbf{p}_{i}\|^{2}$
$\displaystyle\leq\|\mathbf{v}-\mathbf{p}_{i}\|^{2}+\|\mathbf{y}-\mathbf{v}\|^{2}-\|\mathbf{v}-\mathbf{p}_{i}\|\cdot\|\mathbf{y}-\mathbf{v}\|$
$\displaystyle=\|\mathbf{v}-\mathbf{p}_{i}\|\cdot(\|\mathbf{v}-\mathbf{p}_{i}\|-\|\mathbf{y}-\mathbf{v}\|)+\|\mathbf{y}-\mathbf{v}\|^{2}$
$\displaystyle<(1+\varepsilon)\left((1+\varepsilon)-\left(\tfrac{1+\varepsilon}{2}-\frac{1}{2}\sqrt{1-14\varepsilon+\varepsilon^{2}}\right)\right)+\left(\tfrac{1+\varepsilon}{2}-\frac{1}{2}\sqrt{1-14\varepsilon+\varepsilon^{2}}\right)^{2}$
$\displaystyle=(1-\varepsilon)^{2}.$

Because $\mathbf{y}\in D_{\mathbf{0},R}$, there exists a point $\mathbf{x}\in
X$ with $\|\mathbf{x}-\mathbf{y}\|\leq\varepsilon$. By the triangle
inequality, we have $\mathbf{x}\in D_{\mathbf{p}_{1}}\cap D_{\mathbf{p}_{2}}$,
which contradicts the assumption that $\mathscr{D}_{P}$ is an exact cover of
$X$. ∎

We now obtain Theorem 1.3 as a corollary to Proposition 3.3 by setting
$\varepsilon\coloneqq 7-\sqrt{48}$ and
$R\coloneqq\frac{3}{2}\left(1+\varepsilon\right)\approx 1.608$.

###### Proof of Theorem 1.3.

We set $\varepsilon\coloneqq 7-\sqrt{48}$ and
$R\coloneqq\frac{3}{2}(1+\varepsilon)$. Using Proposition 3.3, we obtain that
$D_{\mathbf{0},R}$ is an $\varepsilon$-blocker. Now Proposition 3.3 asserts
that

$\widehat{\sigma}_{2}<N(D_{\mathbf{0},R},\varepsilon).$ (3.11)

It is well-known that the hexagonal lattice $A_{2}$ has covering radius
$\frac{2}{\sqrt{3}}$. In particular, we have

$\mathbb{R}^{2}=\frac{\varepsilon\sqrt{3}}{2}A_{2}+D_{\mathbf{0},\varepsilon}.$
(3.12)

This implies that for every $\mathbf{y}\in\mathbb{R}^{2}$, the set

$X(\mathbf{y})\coloneqq\left(\frac{\varepsilon\sqrt{3}}{2}A_{2}+\mathbf{y}\right)\cap
D_{\mathbf{0},R+\varepsilon}$ (3.13)

is an $\varepsilon$-net of $D_{\mathbf{0},R}$.

Using a computer, one can verify that

$\widehat{\sigma}_{2}<\left|X\left(\begin{pmatrix}\hphantom{+}0.035\\\
-0.055\end{pmatrix}\right)\right|=657.\qed$

##  4 Conclusion

Our main result (Theorems 1.2 and 1.3) is $17\leq\widehat{\sigma}_{2}\leq
656$. An approach for improving the upper bound could be to search for small
$\varepsilon$-nets of $\varepsilon$-blockers and to use Proposition 3.3.

The problem of finding $\widehat{\sigma}_{2}$ admits generalizations to all
dimensions $d\geq 1$ and convex bodies $K\subset\mathbb{R}^{d}$. Let
$\sigma\left(K\right)$ and $\widehat{\sigma}\left(K\right)$ be the largest $n$
such that any $n$-point set in $\mathbb{R}^{d}$ can be covered by disjoint
translates of $K$ or exactly covered by translates of $K$, respectively (and
write $\sigma_{d}$ and $\widehat{\sigma}_{d}$ if $K=B^{d}$). Some of our
methods, such as the Extension Argument and the parameterized family, have
counterparts for other bodies $K$, but our other methods do not necessarily
generalize. The bulldozer needs to be modified if $K$ is not strictly convex.
The proof of Lemma 2.7 is dependent on the geometry of $B^{2}$, and the
redundant disk method also uses specific properties of $A_{2}$.

Sphere packings are mostly empty space in high dimensions. Blichfeldt’s upper
bound of $\frac{d+2}{2}\cdot 2^{-\frac{1}{2}d}$ for the maximum packing
density ([4], or see Section 6.1 of [21]) drops to less than or equal to $0.5$
for $d\geq 6$. The density of the densest known packing in $d=5$ is also below
$0.5$ (see Table 1.2 in Chapter 1 of [6], or [17]). Therefore, we cannot hope
to cover many points by translating a dense packing of unit balls as in
Inaba’s proof [12] (see Appendix A). One possible strategy for “medium”
dimensions around $5$–$10$ is to choose one of several packings based on the
arrangement of $X$.

With regard to lines of further research, we mention the computational
complexity of disk covering. Considering the algorithmic issues that were
discussed in Subsection 1.2, it is natural to ask the following question:
Given $X\in\mathscr{X}$, is it NP-hard to decide whether $X$ has an exact
cover? Ashok, Basu Roy, and Govindarajan (2020) [2] showed that it is NP-hard
to decide the following problem: Given a finite set $\mathscr{R}$ of unit
squares and given an $X\in\mathscr{X}$, is there a subset
$\mathscr{R}^{\prime}\subset\mathscr{R}$ that exactly covers $X$? Their proof
can be easily adapted for a given family $\mathscr{D}$ of unit disks. It might
also be interesting to study the computational complexity if the number of
disks in the exact cover is specified.

### Acknowledgments

Thanks to Michaela Borzechowski, László Kozma, and Günter Rote for their
useful feedback and helpful discussions.

## References

  * [1] Greg Aloupis, Robert A. Hearn, Hirokazu Iwasawa, and Ryuhei Uehara.  Covering points with disjoint unit disks.  In Canadian Conference on Computational Geometry, 2012.  URL: https://api.semanticscholar.org/CorpusID:16280099.
  * [2] Pradeesha Ashok, Aniket Basu Roy, and Sathish Govindarajan.  Local search strikes again: PTAS for variants of geometric covering and packing.  J. Comb. Optim., 39(2):618–635, 2020.  doi:10.1007/s10878-019-00432-y.
  * [3] Ulrich Betke, Martin Henk, and Jörg Wills.  Finite and infinite packings.  Journal für die reine und angewandte Mathematik, 1994:165–192, 01 1994.  doi:10.1515/crll.1994.453.165.
  * [4] Hans Frederick Blichfeldt.  The minimum value of quadratic forms, and the closest packing of spheres.  Mathematische Annalen, 101(1):605–608, 1929.  doi:10.1007/BF01454863.
  * [5] Károly Böröczky, Jr.  Finite Packing and Covering.  Cambridge Tracts in Mathematics. Cambridge University Press, 2004.
  * [6] John H. Conway and Neil J. A. Sloane.  Sphere Packings, Lattices and Groups, volume 290 of Grundlehren der mathematischen Wissenschaften.  Springer-Verlag New York, Inc., 3rd edition, 1999.
  * [7] Veit Elser.  Packing-constrained point coverings, 2011.  arXiv:1101.3468.
  * [8] László Fejes Tóth.  Research problem 13.  Periodica Mathematica Hungarica, 6(2):197–199, 1975.
  * [9] Martin Henk and Jörg M. Wills.  Packings, sausages and catastrophes.  Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry, 2020.  doi:10.1007/s13366-020-00502-x.
  * [10] Phil Hester and Bob Drebin.  2007 Technology Analyst Day, Jul 2007.  URL: http://web.archive.org/web/20081209041620/http://www.amd.com/us-en/assets/content_type/DownloadableAssets/July_2007_AMD_Analyst_Day_Phil_Hester-Bob_Drebin.pdf [cited 2023-10-24].
  * [11] Naoki Inaba, 2008.  URL: http://inabapuzzle.com/hirameki/suuri_4.html.
  * [12] Naoki Inaba, 2008.  URL: http://inabapuzzle.com/hirameki/suuri_ans4.html.
  * [13] Michael Joswig and Thorsten Theobald.  Polyhedral and Algebraic Methods in Computational Geometry.  Universitext. Springer, 2013.
  * [14] Tommi Junttila and Petteri Kaski.  Exact cover via satisfiability: An empirical study.  In David Cohen, editor, Principles and Practice of Constraint Programming – CP 2010, pages 297–304. Springer Berlin Heidelberg, 2010.
  * [15] Donald E. Knuth.  Dancing links, 2000.  arXiv:cs/0011047.
  * [16] Donald E. Knuth.  The Art of Computer Programming, volume 4B.  Pearson Education, Inc., 2023.
  * [17] Gabriele Nebe and Neil J. A. Sloane.  Table of densest packings presently known, Feb 2012.  URL: math.rwth-aachen.de/~Gabriele.Nebe/LATTICES/density.html [cited 2024-01-28].
  * [18] Yosuke Okayama, Masashi Kiyomi, and Ryuhei Uehara.  On covering of any point configuration by disjoint unit disks.  Geombinatorics, 22(1):14–23, 2012.
  * [19] David Wells.  The Penguin Dictionary of Curious and Interesting Geometry.  Penguin Books, 1991.
  * [20] Peter Winkler.  Puzzled: Solutions and sources.  Commun. ACM, 53(9):110, Sep 2010.  doi:10.1145/1810891.1810917.
  * [21] Chuanming Zong.  Sphere Packings.  Universitext. Springer-Verlag New York, Inc., 1999.

Appendix

##  Appendix A Proof of Inaba’s result

Let $K$ be a convex body in $\mathbb{R}^{2}$ and $C\subset\mathbb{R}^{2}$. The
set $C+K\subseteq\mathbb{R}^{2}$ is called a packing (set) of $K$ if

$\left(\mathbf{y}+K\right)\cap\left(\mathbf{z}+K\right)=\emptyset$

for all $\mathbf{y},\mathbf{z}\in C$, $\mathbf{y}\neq\mathbf{z}$. The
proportion of $\mathbb{R}^{2}$ covered by $C+K$ is called the (infinite)
packing density of $C+K$, denoted by $\delta\left(K,C\right)$.

######  Theorem A.1 (Inaba, 2008 [12]).

We have $\sigma_{2}\geq 10$.

###### Proof.

Let $X\in\mathscr{X}$. Place the disk centers at the points of the hexagonal
lattice $A_{2}$, where the minimum distance between distinct points is $2$.
This packing $A_{2}+B^{2}$ has a density of

$\delta\left(B^{2},A_{2}\right)=\frac{\pi}{2\sqrt{3}}\approx 0.9069.$

Let
$\mathscr{A}_{2}\coloneqq\left\\{D_{\mathbf{c}}\subset\mathbb{R}^{2}\,\middle|\,\mathbf{c}\in
A_{2}\right\\}$ be the collection of disks with centers at the points of the
packing set $A_{2}$. We want to find a translation vector
$\mathbf{t}\in\mathbb{R}^{2}$ so that the translated collection
$\mathbf{t}+\mathscr{A}_{2}=\left\\{\mathbf{t}+D\,\middle|\,D\in\mathscr{A}_{2}\right\\}$
of disks covers all points in $X$. Each point $\mathbf{x}\in X$ defines a set

$F_{\mathbf{x}}\coloneqq\left\\{\mathbf{t}\in\mathbb{R}^{2}\,\middle|\,\mathbf{x}\notin
D\text{ for all }D\in\mathbf{t}+\mathscr{A}_{2}\right\\}$ (A.1)

of “forbidden” translation vectors $\mathbf{t}$ that result in a translation
not covering $\mathbf{x}$. The proportion of the area of each $F_{\mathbf{x}}$
in relation to the entire plane is

$1-\delta\left(B^{2},A_{2}\right)\approx 0.0931<\frac{1}{10}.$

Hence, if $\lvert X\rvert\leq 10$, the union of all $F_{\mathbf{x}}$ does not
exhaust the entire plane. Now, some translation vector
$\mathbf{t}^{\prime}\in\mathbb{R}^{2}$ remains that is not part of any
$F_{\mathbf{x}}$, $\mathbf{x}\in X$, and the corresponding covering
$\mathbf{t}^{\prime}+\mathscr{A}_{2}$ contains $X$. Hence $\sigma_{2}\geq 10$.
∎

Inaba’s method applies to any lattice $\Lambda\subset\mathbb{R}^{2}$. The
lower bound for $\sigma_{2}$ obtained by this method is straightforward except
for one wrinkle: if $X\in\mathscr{X}$ with
$\left|X\right|=n=\frac{1}{1-\delta\left(B^{2},\Lambda\right)}$. In this case,
we have $\bigcup_{\mathbf{x}\in X}F_{\mathbf{x}}=\mathbb{R}^{2}$ since each
set $F_{\mathbf{x}}$ is closed, so no $\mathbf{t}^{\prime}$ exists as
described above. Hence we are only guaranteed $\widehat{\sigma}_{2}\geq n-1$
instead of $\widehat{\sigma}_{2}\geq n$, for

$\sigma_{2}\geq\left\lceil\frac{1}{1-\delta\left(B^{2},\Lambda\right)}\right\rceil-1.$
(A.2)

##  Appendix B Technical proofs

In this section we provide several lengthy or technical proofs that would
otherwise cover up the main ideas of Section 2.

###  B.1 Technical proofs for the generalized boundary points

###### Proof of Proposition 2.13.

Write
$T=\operatorname{conv}\left\\{\mathbf{v}^{1},\mathbf{v}^{2},\mathbf{v}^{3}\right\\}$
with the longest side $\overline{\mathbf{v}^{1}\mathbf{v}^{2}}$.

  1. 1.

If $T$ is a right triangle, then the circumcenter of $T$ is at the midpoint
$\mathbf{m}\coloneqq\frac{\mathbf{v}^{1}+\mathbf{v}^{2}}{2}$ of the hypotenuse
$\overline{\mathbf{v}^{1}\mathbf{v}^{2}}$. This side has length less than $2$,
so $R_{T}<1$ and $T\subset D_{\mathbf{m}}$.

  2. 2.

If $T$ is an obtuse triangle, then $T\subset T_{R}$ for any right triangle
$T_{R}$ with hypotenuse
$\operatorname{conv}\left\\{\mathbf{v}^{1},\mathbf{v}^{2}\right\\}$ and which
contains $\mathbf{v}^{3}$. Then by part 1 applied to $T_{R}$, it follows that
$T\subset T_{R}\subset D_{\mathbf{m}}$. ∎

###### Proof of Lemma 2.14.

It suffices to show that $D_{i,j}\cap
T\subseteq\operatorname{BD}_{i,j}\cap\,T$. Without loss of generality, we only
need to prove the Lemma for $i=1$ and $j=2$, and we may assume that
$\mathbf{v}^{1}=\begin{pmatrix}-v\\\ \hphantom{+}0\end{pmatrix}$ and
$\mathbf{v}^{2}=\begin{pmatrix}v\\\ 0\end{pmatrix}$ as in Definition 2.10.
Write

$\displaystyle\operatorname{BD}_{1,2}$
$\displaystyle=\left\\{\begin{pmatrix}z_{1}\\\
z_{2}\end{pmatrix}\in\mathbb{R}^{2}\,\middle|\,\left(z_{1}\right)^{2}+\left(z_{2}+\sqrt{1-v^{2}}\right)^{2}<1\right\\},$
(B.1) $\displaystyle D_{1,2}$ $\displaystyle=\left\\{\begin{pmatrix}z_{1}\\\
z_{2}\end{pmatrix}\in\mathbb{R}^{2}\,\middle|\,\left(z_{1}\right)^{2}+\left(z_{2}+\sqrt{R_{T}-v^{2}}\right)^{2}<R_{T}^{2}\right\\}.$
(B.2)

Let $\mathbf{z}\in D_{1,2}\cap T$. We substitute (B.2) into (B.1) for

$\displaystyle\left(z_{1}\right)^{2}+\left(z_{2}+\sqrt{1-v^{2}}\right)^{2}$
$\displaystyle<$ $\displaystyle
R_{T}^{2}-\left(z_{2}+\sqrt{R_{T}^{2}-v^{2}}\right)^{2}+\left(z_{2}+\sqrt{1-v^{2}}\right)^{2}$
$\displaystyle=$ $\displaystyle
1-2z_{2}\left(\sqrt{R_{T}^{2}-v^{2}}-\sqrt{1-v^{2}}\right).$

The rightmost quantity is less than $1$ since $z_{2}\geq 0$ and $R_{T}^{2}>1$,
so $\mathbf{z}\in\operatorname{BD}_{1,2}\cap\,T$. ∎

###  B.2 Technical proofs for the redundant disk method

###### Proof of Proposition 2.21.

Assume that $\mathbf{y}=\begin{pmatrix}-\sqrt{3}\\\ 1\end{pmatrix}$ and
$\mathbf{z}=\begin{pmatrix}0\\\ 0\end{pmatrix}$. Let $\mathbf{w}^{\rho}$ be
the point of intersection between
$\operatorname{bd}D_{(-\sqrt{3},1)^{\mathsf{T}},\rho}$ and
$\operatorname{bd}D_{\mathbf{0},\rho}$ with higher $y$-coordinate (see Figure
13); this point exists because $\rho\geq 1$. We will show that the tangent
line $L^{\rho}\left(\mathbf{w^{\rho}}\right)$ has slope $\geq 1$.

Figure 13: The disks $D_{\mathbf{w}}$ (black) and $D_{\mathbf{w},1.08}$ (blue)
for $\mathbf{w}=\mathbf{y}=\begin{pmatrix}-\sqrt{3}\\\ 1\end{pmatrix}$ (top
left), $\mathbf{w}=\mathbf{z}=\begin{pmatrix}0\\\ 0\end{pmatrix}$ (lower
right), and $\mathbf{x}=\begin{pmatrix}-\sqrt{3}\\\ -1\end{pmatrix}$ (bottom
left), the point $\mathbf{w}^{1.08}$ (red), and the line
$L^{1.08}\left(\mathbf{w^{1.08}}\right)$ (red).

The general case reduces to this special case by the symmetry of $A_{2}$ and
the circle.

To calculate the coordinates of the intersection point $\mathbf{w}^{\rho}$, we
parameterize the boundary circles of $D_{\mathbf{y}}$ and $D_{\mathbf{z}}$ by

$\displaystyle\mathbf{p}_{\mathbf{y}}\left(\phi\right)$
$\displaystyle=\begin{pmatrix}-\sqrt{3}\\\
1\end{pmatrix}+\rho\begin{pmatrix}\hphantom{+}\cos\left(\phi-\frac{2\pi}{3}\right)\\\
-\sin\left(\phi-\frac{2\pi}{3}\right)\end{pmatrix},$
$\displaystyle\mathbf{p}_{\mathbf{z}}\left(\phi\right)$
$\displaystyle=\rho\begin{pmatrix}\cos\phi\\\ \sin\phi\end{pmatrix},$

for $\phi\in\left[0,2\pi\right]$, so that

$\displaystyle D_{\mathbf{y}}$
$\displaystyle=\left\\{\mathbf{p}_{\mathbf{y}}\left(\phi\right)\,\middle|\,0\leq\phi\leq
2\pi\right\\},$ $\displaystyle D_{\mathbf{z}}$
$\displaystyle=\left\\{\mathbf{p}_{\mathbf{z}}\left(\phi\right)\,\middle|\,0\leq\phi\leq
2\pi\right\\}.$

The parameterization of $D_{\mathbf{z}}$ is as usual, but the parameterization
of $D_{\mathbf{y}}$ is offset and moves clockwise so that
$\mathbf{p}_{\mathbf{y}}\left(\phi\right)$ and
$\mathbf{p}_{\mathbf{z}}\left(\phi\right)$ are always equidistant from the
tangent line common to $D_{\mathbf{y}}$ and $D_{\mathbf{z}}$. In particular,
$\mathbf{w}^{\rho}=\mathbf{p}_{\mathbf{y}}\left(\phi\right)=\mathbf{p}_{\mathbf{z}}\left(\phi\right)$
for the smallest positive $\phi$ such that
$\mathbf{p}_{\mathbf{y}}\left(\phi\right)=\mathbf{p}_{\mathbf{z}}\left(\phi\right)$.
This equality is equivalent to the system

$\displaystyle\rho\cos\phi$
$\displaystyle=-\sqrt{3}+\rho\cos\left(\phi-\frac{2\pi}{3}\right),$
$\displaystyle\rho\sin\phi$
$\displaystyle=1-\rho\sin\left(\phi-\frac{2\pi}{3}\right).$

The smallest positive solution of either equation is given by

$\phi=\phi_{\rho}\coloneqq\frac{5\pi}{6}-\operatorname{arcsec}\left(\rho\right),$

which yields

$\mathbf{w}^{\rho}=\mathbf{p}_{\mathbf{z}}\left(\phi_{\rho}\right)=\frac{1}{2}\begin{pmatrix}-\sqrt{3}+\sqrt{\rho^{2}-1}\\\
\sqrt{3}\sqrt{\rho^{2}-1}+1\end{pmatrix}.$

Hence $L^{\rho}\left(\mathbf{w^{\rho}}\right)$ is given by the equation

$y=\frac{\sqrt{3}-\sqrt{\rho^{2}-1}}{\sqrt{3}\sqrt{\rho^{2}-1}+1}\left(x-\frac{1}{2}\left(-\sqrt{3}+\sqrt{\rho^{2}-1}\right)\right)+\frac{1}{2}\left(\sqrt{3}\sqrt{\rho^{2}-1}+1\right),$

whose slope is greater than or equal to $1$ if $\rho\leq\sqrt{6}-\sqrt{2}$. ∎

###### Proof of Proposition 2.22.

Note that $R^{\rho}\left(\mathbf{y},\mathbf{z}\right)$ is a subset of the
half-space $S\coloneqq\left\\{\mathbf{w}\in\mathbb{R}^{2}\,\middle|\,w_{1}\leq
w_{1}^{\rho}\right\\}$, where $\mathbf{w}^{\rho}$ is the rightmost “vertex” of
$R^{\rho}\left(\mathbf{y},\mathbf{z}\right)$ as in the proof of Proposition
2.21. So we may restrict our attention to the subset
$\left(\operatorname{conv}X\right)\cap S$ of $\operatorname{conv}X$. The
interior angle at $\mathbf{v}^{1}$ is at most $\frac{\pi}{2}$ and
$\overline{\mathbf{v}^{1}\mathbf{v}^{2}}$ and
$\overline{\mathbf{v}^{1}\mathbf{v}^{3}}$ have equal and opposite slopes, so
these slopes have absolute values of at most $1$. However, by Proposition
2.21, the slope of the upper arc of
$\operatorname{bd}\left(R^{\rho}\left(\mathbf{y},\mathbf{z}\right)\right)$ is
always greater than or equal to $1$. So, by the Mean Value Inequality and the
symmetry of the circle, we have $\left(\operatorname{conv}X\right)\cap
S\subseteq D_{\mathbf{z}}$. ∎