# (Re)packing Equal Disks into Rectangle††thanks: The research leading to
these results has received funding from the Research Council of Norway via the
project BWCA (grant no. 314528), the European Research Council (ERC) via grant
LOPPRE, reference 819416, and Israel Science Foundation (ISF) grant no.
1176/18. 111A preliminary version of this article [13] appears in the
proceedings of the 49th International Colloquium on Automata, Languages, and
Programming, ICALP 2022.

Fedor V. Fomin  Department of Informatics, University of Bergen, Norway. Petr
A. Golovach11footnotemark: 1 Tanmay Inamdar11footnotemark: 1 Saket
Saurabh11footnotemark: 1 The Institute of Mathematical Science, HBNI, Chennai,
India Meirav Zehavi Ben-Gurion University of the Negev, Beer-Sheva, Israel

###### Abstract

The problem of packing of equal disks (or circles) into a rectangle is a
fundamental geometric problem. (By a packing here we mean an arrangement of
disks in a rectangle without overlapping.) We consider the following
algorithmic generalization of the equal disk packing problem. In this problem,
for a given packing of equal disks into a rectangle, the question is whether
by changing positions of a small number of disks, we can allocate space for
packing more disks. More formally, in the repacking problem, for a given set
of $n$ equal disks packed into a rectangle and integers $k$ and $h$, we ask
whether it is possible by changing positions of at most $h$ disks to pack
$n+k$ disks. Thus the problem of packing equal disks is the special case of
our problem with $n=h=0$.

While the computational complexity of packing equal disks into a rectangle
remains open, we prove that the repacking problem is NP-hard already for
$h=0$. Our main algorithmic contribution is an algorithm that solves the
repacking problem in time $(h+k)^{\mathcal{O}(h+k)}\cdot|I|^{\mathcal{O}(1)}$,
where $I$ is the input size. That is, the problem is fixed-parameter tractable
parameterized by $k$ and $h$.

##  1 Introduction

Packing of equal circles inside a rectangle or a square is one of the oldest
packing problems. In addition to many common-life applications, like packing
bottles or cans in a box [17], packings of circles have a variety of
industrial applications, including circular cutting problems, communication
networks, facility location, and dashboard layout. We refer to the survey of
Castillo, Kampas, and Pintér [5] for an interesting overview of industrial
applications of circle packings.

The mathematical study of packing equal circles can be traced to Kepler [21].
Packing of circles also poses exciting mathematical and algorithmic
challenges. After the significant efforts spent on packing for several decades
[29, 32, 24, 27, 23, 31, 28, 12], optimal packings of equal circles inside a
square are known only for instances of up to tens of circles [8, 30]. The
computational complexity of packing of equal circles (NP-hardness or
membership in NP) remains elusive. For packing circles with different radii,
Demaine, Fekete, and Lang claimed NP-hardness [10]. See also the work of
Abrahamsen, Miltzow, and Seiferth [1] for a generic framework for establishing
$\exists\mathbb{R}$-completeness for packing problems.

Our paper establishes several results on computational and parameterized
complexity of a natural generalization of packing equal circles inside a
rectangle. A remark in the terminology is in order. In the literature on
packing, both terms, circles and disks, could be found. While the term circle
is much more popular than disk, we decided to use disks for the following
reason: In our hardness proof, it is more convenient to operate with open
disks. Thus all disks we consider are open and unit (that is of radius one).
Let us remind, that a family of disks forms a _packing_ if they are pairwise
nonintersecting.222In the literature, it is often required for geometric
packings that a packing should be maximal. In particular, for disk packing,
every disk should touch either the bounding rectangle or another disk.
However, in our problem, the task is to add a specified number of new disks to
a given family and this makes the maximality condition in our case very
artificial. In our problem, we have a packing of disks in a rectangle, and the
question is whether we can allocate some space for more disks by relocating a
small amount of disks. More precisely, we consider the following problem. See
Figure 1 for an example.

Input: A packing $\mathcal{P}$ of $n$ unit disks inside a rectangle $R$ and
two integers $h,k\geq 0$. Task: Decide whether there is a packing
$\mathcal{P}^{*}$ of $n+k$ unit disks inside $R$ obtained from $\mathcal{P}$
by adding $k$ new disks and relocating at most $h$ disks of $\mathcal{P}$ to
new positions. Disk Repacking parameterized by

Figure 1: For a packing $\mathcal{P}$ of disks $A$–$F$, integers $h=2$, and
$k=2$, the repacking $\mathcal{P}^{*}$ of $\mathcal{P}$ is obtained by
relocating disks $C$ and $F$, and by adding disks $G$ and $H$.

Thus when $n=0$, that is, initially there are no disks inside the rectangle,
this is the classical problem of packing equal circles inside a rectangle.

### Related Work on Geometric Packing.

Packing problems have received significant attention from the viewpoint of
approximation algorithms. For the sake of illustration, let us mention a few
examples. In $2$D Geometric Bin Packing, which is a variant of classical Bin
Packing, the goal is to pack a given collection of rectangles into the minimum
number of unit square bins. Typically, it is required that the rectangles be
packed in an axis-parallel manner. There has been a long series of results on
this problem, culminating in the currently known best approximation given by
Bansal and Khan [3]. A related problem is that of $2$D Strip Packing problem,
where the task is to pack a given set of rectangles into an infinite strip of
the given width, so as to minimize the height of packing. This problem has
been studied from the context of approximation [18, 20] as well as
parameterized [2] algorithms. Finally, we mention the Geometric Knapsack
problem, which is also closely related to Geometric Bin Packing. In Geometric
Knapsack, we are given a collection of rectangles, where each rectangle has an
associated profit. The goal is to pack a subset of the given rectangles
(without rotation) in an axis-aligned square knapsack, so as to maximize the
total profit of the packed rectangles. Currently, the best approximation is
given by Galvez et al. [15]. A detailed survey of the literature on the
results of these problems is beyond the scope of this work – we direct an
interested reader to the cited works and references therein and the survey
paper of Christensen et al. [6]. However, we would like to highlight an
important difficulty in Disk Repacking—which is the focus of this work—as
compared to the aforementioned geometric packing problems, namely, that
packing disks in a rectangle requires the use of intricate geometric arguments
as compared to packing rectilinear objects (such as rectangles) in a
rectilinear container (such as a unit square, or an infinite strip).

### Our Results.

We show that Disk Repacking is $\operatorname{NP}$-hard even if the parameter
$h=0$ – we call this special case of problem Disk Appending.

######  Theorem 1.

Disk Appending is $\operatorname{NP}$-hard when constrained to the instances
$(R,\mathcal{P},k)$ where $R=[0,a]\times[0,b]$ for positive integers $a$ and
$b$ and the centers of all disks in $\mathcal{P}$ have rational coordinates.
Furthermore, the problem remains $\operatorname{NP}$-hard when it is only
allowed to add new disks to $\mathcal{P}$ with rational coordinates of their
centers.

From the positive side, we show that Disk Repacking is $\operatorname{FPT}$
when parameterized by $k$ and $h$. As it is common in Computational Geometry,
we assume the _real RAM_ computational model, that is, we are working with
real numbers and assume that basic operations can be executed in unit time. We
use $|I|$ to denote the input size.

######  Theorem 2.

The Disk Repacking problem is $\operatorname{FPT}$ when parameterized by
$k+h$. Specifically, it is solvable in time
$(h+k)^{\mathcal{O}(h+k)}\cdot|I|^{\mathcal{O}(1)}$.

Theorem 2 also appears to be handy for approximating the maximum number of
disks that can be added to a packing. In the optimization variant of Disk
Repacking, called Max Disk Repacking, we are given a packing $\mathcal{P}$ of
$n$ disks in a rectangle $R$ and an integer $h$, and the task is to maximize
the number of new disks that can be added to the packing if we are allowed to
relocate at most $h$ disks of $\mathcal{P}$. By combining Theorem 2 with the
approach of Hochbaum and Maass [19], we prove that the optimization variant of
Disk Repacking admits the parameterized analog of EPTAS for the
parameterization by $h$. More precisely, we prove the following theorem.

######  Theorem 3.

For any $0<\varepsilon<1$, there exists an algorithm that, given an instance
$(\mathcal{P},R,h)$ of Max Disk Repacking, returns a packing $\mathcal{P}^{*}$
into $R$ with at least $n+(1-\varepsilon)\cdot{\sf OPT}_{h}$ disks in time
$\big{(}\frac{h+1}{\varepsilon}\big{)}^{\mathcal{O}(h/\varepsilon+1/\varepsilon^{2})}\cdot|I|^{\mathcal{O}(1)}$,
where ${\sf OPT}_{h}$ is the maximum number of disks that can be added to the
input packing if we can relocate at most $h$ disks.

##  2 Preliminaries

### Disks and rectangles.

For two points $A$ and $B$ on the plane, we use $AB$ to denote the line
segment with endpoints in $A$ and $B$. The _distance_ between
$A=(x_{1},y_{1})$ and $B=(x_{2},y_{2})$ or the _length_ of $AB$, is
$|AB|=\|A-B\|_{2}=\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}$. The _(open
unit) disk_ with a _center_ $C=(c_{1},c_{2})$ on the plane is the set of
points $(x,y)$ satisfying the inequality $(x-c_{1})^{2}+(y-c_{2})^{2}<1$.
Whenever we write “disk” we mean an open unit disk. Throughout the paper, we
assume that considered input rectangles $R=[0,a]\times[0,b]$ for some $a,b>0$.

### Parameterized Complexity.

We refer to the book of Cygan et al. [9] for introduction to the area and
undefined notions. A _parameterized problem_ is a language
$L\subseteq\Sigma^{*}\times\mathbb{N}$, where $\Sigma^{*}$ is a set of strings
over a finite alphabet $\Sigma$. An input of a parameterized problem is a pair
$(x,k)$, where $x\in\Sigma^{*}$ and $k\in\mathbb{N}$ is a _parameter_. A
parameterized problem is _fixed-parameter tractable_ (or $\operatorname{FPT}$)
if it can be solved in time $f(k)\cdot|x|^{\mathcal{O}(1)}$ for some
computable function $f$.

### Systems of Polynomial Inequalities.

In our algorithms, we will need to find suitable locations for new disks that
need to be added such that the locations are compatible with an existing
packing. We will achieve this by solving systems of polynomial inequalities.
We refer to the book of Basu, Pollack, and Roy [4] for basic tools. We use the
following result.

######  Proposition 1 (Theorem 13.13 in [4]).

Let $R$ be a real closed field, and let $\mathcal{P}\subseteq
R[X_{1},\ldots,X_{\ell}]$ be a finite set of $s$ polynomials, each of degree
at most $d$, and let

$(\exists X_{1})(\exists X_{2})\ldots(\exists
X_{\ell})F(X_{1},X_{2},\ldots,X_{\ell})$

be a sentence, where $F(X_{1},\ldots,X_{\ell})$ be a quantifier-free boolean
formula involving $\mathcal{P}$-atoms of type $P\odot 0$, where
$\odot\in\\{=,\neq,>,<\\}$, and $P$ is a polynomial in $\mathcal{P}$. Then,
there exists an algorithm to decide the truth of the sentence with complexity
$s^{\ell+1}d^{\mathcal{O}(\ell)}$ in $D$, where $D$ is the ring generated by
the coefficients of the polynomials in $\mathcal{P}$.

Furthermore, a point $(X_{1}^{*},\ldots,X_{\ell}^{*})$ satisfying
$F(X_{1},\ldots,X_{\ell})$ can be computed in the same time by Algorithm 13.2
(sampling algorithm) of [4] (see Theorem 13.11 of [4]). Note that because we
are using the real RAM model in our algorithms, the complexity is stated with
respect to the natural parameters.

##  3 Hardness of Disk Appending

In this section, we prove Theorem 1 on the hardness of Disk Appending. Recall,
that Disk Appending is the special case of Disk Repacking with $h=0$. We use
the following auxiliary notation in this section.

We use standard graph-theoretic terminology and refer to the textbook of
Diestel [11] for missing notions. We consider only finite undirected graphs.
For a graph $G$, $V(G)$ and $E(G)$ are used to denote its vertex and edge
sets, respectively. For a vertex $v\in V(G)$, $N_{G}(v)=\\{u\in V(G)\mid uv\in
E(G)\\}$ denotes the _neighborhood_ of $v$, and $d_{G}(v)=|N_{G}(v)|$ is the
_degree_ of $v$. A graph is _cubic_ if every vertex has degree three. A graph
$G$ is _planar_ if it has a plane embedding, that is, it can be drawn on the
plane without crossing edges. A _rectilinear_ embedding is a planar embedding
of $G$ such that vertices are mapped to points with integer coordinates and
each edge is mapped into a broken line consisting of an alternate sequence of
horizontal and vertical line segments. The switches between horizontal and
vertical lines are called _bends_. The _area_ of an embedding is minimum
$(b_{1}-a_{1})\times(b_{2}-a_{2})$ such that all points of the embedding are
in the rectangle $[a_{1},b_{1}]\times[a_{2},b_{2}]$.

We say that a point $X$ is _properly inside_ of a polygon $P$ if it is inside
$P$ but $X$ is not on the boundary; if we say that $X$ is inside $P$, we allow
it to be on the boundary. A disk is _(properly) iniside_ of a polygon $P$ if
every point of the disk is (properly) inside of $P$.

We restate the main theorem of the section.

See 1

### Proof of Theorem 1: Overview.

We reduce from the Independent Set problem. Let us recall that in this
problem, for a given a graph $G$ and a positive integer $k$, the task is to
decide whether $G$ contains an independent set, that is a set of pairwise
nonadjacent vertices, of size at least $k$. It is well-known that Independent
Set is $\operatorname{NP}$-complete on cubic planar graphs [16] (see also [25]
for an explicit proof).

Before diving into the details, which are pretty technical, let us outline the
main ideas of the reduction. Let $G$ be a graph and assume that $\ell_{e}$ are
positive integers given for all $e\in E(G)$. Suppose that $G^{\prime}$ is
obtained from $G$ by subdividing each edge $e$ by $2\ell_{e}$ times (the edge
subdivision operation for $e=uv$, deletes $e$ and creates a new vertex $w_{e}$
adjacent to both $u$ and $v$). Then it can be shown that $G$ has an
independent set of size $k$ if and only if $G^{\prime}$ has an independent set
of size $k+\sum_{e\in E(G)}\ell_{e}$. We exploit this observation. Given a
rectilinear embedding of a cubic planar graph $G$, for each vertex of $G$, we
create a _node_ area formed by surrounding disks. We can place an additional
disk in such an area and this encodes the inclusion of the corresponding
vertex to an independent set. Then we join the areas created for vertices by
_channels_ corresponding to subdivided edges. Similarly to node areas,
channels are formed by surrounding disks. Each channel contains even number of
positions where new disks can be placed, and these positions are divided into
“odd” and “even” in such a way that we can put disks in either all odd or all
even positions but no disks could be placed in adjacent even and odd
positions. Thus node areas and channels are used to encode a graph, and then
we fill the space around them by _filler_ disks that prevent placing any new
disk outside node areas and channels. Then placing new disks corresponds to
the choice of an independent set in a subdivided graph. Further in this
section, we give a formal proof. To avoid unnecessary complications in the
already technical proof, we allow algebraic number parameters in our reduction
and then explain how we can get rid of these constraints.

### Proof of Theorem 1: Constructing channels and node areas.

Our construction of node areas and channels follows a rectilinear embedding of
a planar graph and we use that fact that rectilinear embeddings can be
constructed efficiently. In particular, the following theorem was shown by
Liu, Morgana, and Simeone [22].

######  Proposition 2 ([22]).

Every $n$-vertex planar graph of maximum degree at most $4$ admits a
rectilinear embedding with at most $3$ bends for every edge with the area
$\mathcal{O}(n^{2})$. Furthermore, such an embedding can be constructed in
$\mathcal{O}(n)$ time.

We use Proposition 2 to construct node area and channels. Let $G$ be an
$n$-vertex cubic graph. We assume that we are given a rectilinear embedding of
$G$ with the properties guaranteed by Proposition 2. We also assume without
loss of generality that the length of every segment of a broken line
representing an edge is at least three. This can be achieved by replacing
every vertex or bend point $(x,y)$ of the embedding by the point $(3x,3y)$ and
the corresponding adjustment of the segments in the broken lines. Notice that
every segment in the embedding contains at least two integer points different
from the endpoints of the segment. For each integer point of the rectangle
containing the embedding, we construct a $2c\times 2c$ square tile, where $c$
is a sufficiently big odd positive integer (the choice of $c$ will be
explained later), of one of the following four types: (i) node tile containing
a node area, (ii) horizontal/vertical channel, (iii) bend channel tiles to
form channels, and (iv) filler tile to fill forbidden areas. Then we use these
tiles to encode a graph as it is shown in Figure 2 sticking the tiles together
following the embedding.

$G$Rectilinear
embedding$B$$C$$C$$C$$C$$C$$C$$C$$C$$C$$C$$C$$C$$C$$C$$C$$C$$C$$B$$B$$B$$N$$N$$N$$N$$C$$C$$C$$C$$F$$F$$F$$F$$F$$F$$F$$F$$F$$F$$F$$F$$F$$F$$F$$F$$F$$F$$C$$C$

Figure 2: Encoding of $G$; the node areas and channels are shown in red, the
node, channel, bend and filler tiles are labeled by $N$, $C$, $B$ and $F$,
respectively.

Now we describe these tiles. We start with the construction of the filler tile
which is trivial—we simply fill a $2c\times 2c$ square by disks as it is shown
in Figure 3.

\begin{picture}(2424.0,2424.0)(739.0,-1723.0)\end{picture}

Figure 3: The filler tile.

Next, we deal with channel tiles. The construction of these tiles is more
complicated. In particular, we need three kinds of such tiles because we have
to adjust parities and join them together with other tiles. However, the basic
idea is the same for all kinds. Consider four touching disks with centers $A$,
$B$, $C$, and $D$ shown in Figure 4 (a). Note that $h=2+\sqrt{3}$,
$\ell=|AC|=|BC|=2\sqrt{2+\sqrt{3}}$, and the angle $\alpha=\pi/12$. Then we
can make the straightforward observation that, given disks with centers in
$A$, $B$ and $C$, every disk with its center in the triangle $ABC$ has its
center in $D$. Then extending this, we can make the following observation
about the configuration of disks shown in Figure 4 (b). We call such a
configuration of disks a _basic channel_ of size $r$. When we say that a disk
is placed or added, we mean that the disk should be disjoint with other disks.
Also we say that a disk is _inside_ of a channel if its center is in
$B_{1}A_{1}A_{r}B_{r}$.

$X_{r-1}$$\alpha$$h$$\ell$$A$$B$$C$$D$$2$$2$$A_{1}$$A_{r}$$B_{1}$$Y_{r}$$B_{r}$a)b)$X_{1}$$Y_{2}$

Figure 4: The basic channel of size $r$; the disks shown in red and blue are
not parts of the channel – they show places where new disks can be inserted.

######  Observation 1.

Given disks with centers in $A_{1},\ldots,A_{r}$ and $B_{1},\ldots,B_{r}$ as
it is shown in Figure 4 (b), any disk placed properly inside the quadrilateral
$A_{1}B_{1}B_{r}A_{r}$ has its center in one of the points
$X_{1},\ldots,X_{r-1}$ or $Y_{2},\ldots,Y_{r}$. Furthermore, if a disk with
its center in $X_{i}$ ($Y_{i}$, respectively) is placed in the quadrilateral,
then no other disk can have its center in $Y_{i}$ or $Y_{i+1}$ ($X_{i-1}$ or
$X_{i}$, respectively).

We use basic channels to construct channel, bend and node tiles. In
particular, we construct the _straight_ channel tile from the basic channel of
size $c$ by deleting the left bottom disk and filling the space outside the
channel in the $2c\times 2c$ square by additional disks as it is shown in
Figure 5 (a). The disks with the centers in $A$ and $B$ are called _poles_.
They are identified with poles of other tiles to join them together. We refer
to the basic channel inside the tile as the channel of the tile.

$4$$B$$h$$A$$2$$4$$2$$c$$c$$2c$$X$$Y$$h$$A$$2$$4$$2$$c$$c$$X$$B$$Y$$2c$a)b)$4$

Figure 5: The straight channel tile (a) and the twisted channel tile (b). The
disks shown in red and blue are not parts of the gadgets, the disks shown in
magenta are used to fill space.

However, we need some further configurations of disks, because we have to
adjust parities and distances in tiles, and also we have to joint tiles with
each other. In particular, to join channel tiles with other tiles, we have to
twist basic channels in some of them as it is shown in Figure 6 (a). Then the
following observation is straightforward.

b)$B_{1}$$X_{1}$$X_{2}$$Y_{1}$$Y_{2}$$Z_{1}$$Z_{2}$$A_{1}$$A_{2}$$B_{2}$$3$$3$$A_{1}$$A_{2}$$B_{1}$$B_{2}$$X_{1}$$X_{2}$$Y_{1}$$Y_{2}$a)

Figure 6: Twisting (a) and level adjustment (b).

######  Observation 2.

Given disks with centers in $A_{1},A_{2}$ and $B_{1},B_{2}$ as it is shown in
Figure 6 (a), the following holds:

  * •

if two disks with their centers in $X_{1}$ and $X_{2}$ are placed as it is
shown in the figure, then at most two disks with their centers inside
$A_{1}B_{1}B_{2}A_{2}$ can be added, and if two disks are placed in
$A_{1}B_{1}B_{2}A_{2}$ they have centers in $Y_{1}$ and $Y_{2}$, respectively,

  * •

if two disks with their centers in $Z_{1}$ and $Z_{2}$ are placed as it is
shown in the figure, then at most one disk with its center
$A_{1}B_{1}B_{2}A_{2}$ can be added.

We construct the _twisted_ channel tile (see Figure 5 (b)) similarly to the
straight channel tile – the difference is that we insert one twist using 2.
The crucial properties of straight and twisted channel tiles implied by 1 and
2 are given in the following lemma. We say that a point is _inside a tile_ if
it is inside of the $2c\times 2c$ square in the tile.

######  Lemma 1.

At most $c+1$ new disks having their centers in the (straight, twisted)
channel tile can be added and it is possible to place $c+1$ disks. Moreover,
the following holds:

  * •

only disks inside channels can be added,

  * •

if exactly $c+1$ disks are placed, then two of them have their centers in $X$
and $Y$ (see Figure 5),

  * •

it is possible to place $c$ disks that have no centers in $X$ and $Y$, but
then they are completely inside the tile and it is impossible to place an
additional disk having its center inside the tile.

We need a modification of the straight tile to adjust parities. Notice that
disks placed inside a basic channel may be on different levels (see the red
and blue disks in Figure 4 (b) with their centers on the red and blue line,
respectively). Hence, we need to adjust levels as it is shown in Figure 6 (b).
Then we observe the following.

######  Observation 3.

Suppose that we are given disks with centers in $A_{1},A_{2}$ and
$B_{1},B_{2}$ as it is shown in Figure 6 (b). Then if there are two disks with
their centers in $X_{1}$ and $X_{2}$ ($Y_{1}$ and $Y_{2}$, respectively), then
at most one disjoint disk with its center in $A_{1}B_{1}B_{2}A_{2}$ can be
added.

To fix parity, we also have to adjust distances. For this, we observe that we
can insert gaps of length $s<\sqrt{4\sqrt{3}-3}-1$ between disks in basic
channels as it is shown in Figure 7 (a).

$Z^{\prime}$$X$$Y$$A_{1}$$A_{2}$$B_{1}$$B_{2}$$s$$s$a)$Y$$A_{2}$$B_{1}$$B_{2}$b)$X$$A_{1}$$Z$

Figure 7: Gap insertion.

######  Observation 4.

Given disks with centers in $A_{1},A_{2}$ and $B_{1},B_{2}$ as it is shown in
Figure 7 (a), at most one disk with its center inside the quadrilateral
$A_{1}B_{1}B_{2}A_{2}$ can be added. Furthermore, if a disk has a center
inside $A_{1}B_{1}B_{2}A_{2}$, then this disk intersects the disk with its
center in $X$ or the disk with its center in $Y$.

###### Proof.

The claim follows from the following geometrical observation illustrated in
Figure 7 (b). Suppose that the gap is exactly $\sqrt{4\sqrt{3}-3}-1$ and there
are disks with centers in $A_{1}$, $A_{2}$, $B_{1}$, $B_{2}$, $X$ and $Y$.
Then any disk with its center inside $A_{1}B_{1}B_{2}A_{2}$ either has its
center in $Z$ and touches the disks with centers in $X$, $A_{2}$ and $Y$ or
has its center in $Z^{\prime}$ and touches the disks with centers $X$, $B_{1}$
and $Y$; note that $Z$ and $Z^{\prime}$ are uniquely defined by these touching
conditions. Therefore, if $s<\sqrt{4\sqrt{3}-3}-1$, a new disk cannot be
inserted in $A_{1}B_{1}B_{2}A_{2}$. ∎

Now we construct the _parity adjustment_ channel tile from the basic channel
of size $c-1$ by introducing two gaps of size $1/2<\sqrt{4\sqrt{3}-3}-1$ and
one level adjustment as it is shown in Figure 8. Similarly to Lemma 1, we have
the following properties by making use of 1, 3 and 4.

$1/2$$h$$A$$2$$4$$2$$c$$c$$X$$4$$2c$$Y$$B$$1/2$$1/2$$1/2$

Figure 8: The parity adjustment channel tile. The disks shown in red and blue
are not parts of the gadgets, the disks shown in magenta are used to fill
space.

######  Lemma 2.

At most $c$ new disks having their centers in the parity adjustment channel
tile can be added and it is possible to place $c$ disks. Moreover, only disks
inside the channel of the tile can be added and if $c$ disks are added then
either one of them has its center in $X$ (see Figure 8) and it is impossible
to add the disk having its center in $Y$ or, symmetrically, one disk has its
center in $Y$ and the disk centered in $X$ cannot be inserted.

Bottom
channel$c$$c$$c$$c$$A$$X$$B$$Y$$1/2$$1/2$$1/2$$1/2$b)$h$$A$$B$$C$$D$$X$$Y$$Z$$\beta$$\alpha$$O$$h$a)Left
channel

Figure 9: The bend tile. The disks shown in red and blue are not parts of the
gadgets, the disks shown in magenta are used to fill space.

We use basic channels and apply gap insertions to construct the bend tile.
Additionally, we observe that we can “bend” basic channels (see Figure 9 (a)).
Consider five touching disks with centers $A$, $B$, $C$, $D$, and $O$ shown in
Figure 9 (a); $h=2+\sqrt{3}$, $|OA|=|OD|=\ell=2\sqrt{2+\sqrt{3}}$,
$|OB|=|OC|=2\sqrt{2+\sqrt{2}}$, and the angles $\alpha=\pi/12$ and
$\beta=\pi/8$. Then we can make the following observation.

######  Observation 5.

Given disks with their centers in $A$, $B$, $C$, $D$ and $O$, only disks with
centers in $X$, $Y$ and $Z$ can have their centers in $ABCDO$. Moreover, if
there is a disk with center in $X$ or $Z$, then the disk with its center in
$Y$ cannot be added, and if there is the disc with its center in $Y$, then no
disk having its center if $X$ or $Z$ can be added.

5 allows to construct the bend tile (see Figure 9 (b)). We use the
configuration of disks from Figure 9 (a) and attach two basic channels called
_left_ and _bottom_ channels, respectively. To adjust distances, we insert two
gaps of size $1/2$ into each channels. Then the remaining space if filled by
disks. The disks with their centers in $A$ and $B$ are _poles_ of the tile. In
the same way as with channel tiles, we have the following properties by making
use of 1, 4 and 5.

######  Lemma 3.

At most $c-1$ new disks having their centers in the bend tile can be added and
it is possible to place $c-1$ disks. Moreover, the following holds:

  * •

disks can be placed only inside the channel,

  * •

if exactly $c-1$ disks are placed, then two of them have their centers in $X$
and $Y$ (see Figure 9 (a)),

  * •

it is possible to place $c-2$ disks that have no centers in $X$ and $Y$, but
then they are completely inside the tile and it is impossible to place an
additional disk having its center inside the tile.

$F$$B$$X$$Y$$Z$$A$$C$$h^{\prime}$$O$$Y$$X$$Z$$A$$C$$B$$D$$E$$\alpha$$\gamma$$U$$W$$h$a)b)

Figure 10: Node area.

The construction of the node tile is based on the following geometric
observations. Consider an equilateral triangle $ABC$ with sides of length two
as shown in Figure 10 (a), $h^{\prime}=2\sqrt{3}$. Suppose that there are
disks with centers in $A$, $B$ and $C$. Then it is possible to place at most
three disks with centers in the triangle $ABC$, and if exactly three disks are
placed, then they have their centers in $X$, $Y$ and $Z$ and touch each other.
Furthermore, if a disk having its center properly inside $ABC$ is placed, then
no other disk with its center inside the triangle can be added. We exploit
this property and add a basic channel as it is shown in Figure 10 (b). The
point $O$ is the center of $ABC$, that is, $|OA|=|OB|=|OC|$. Recall that
$h=2+\sqrt{3}$ and $\alpha=\pi/12$. We set $\gamma=\pi/3-\pi/12=\pi/4$. This
gives us the configuration of disks with the following properties summarized
in the next observation.

######  Observation 6.

Given disks with centers in $A$, $B$, $C$, $D$, $E$ and $F$ as it is shown in
Figure 10 (b), the following is fulfilled:

  * •

at most one disk with its center in $BCD$ can be added,

  * •

if there is a disk with its center either in $Y$ or $U$, then no other disk
can have its center properly in $BCD$,

  * •

if there are disks with their centers in $O$ and $W$, then a disk with its
center in $BCD$ can be added,

  * •

if there is a disk having its center properly inside $ABC$, then no other disk
with its center inside $ABC$ can be added.

We also using an easy observation that the basic channel construction allows
to bend them by $\pi/6$ or $\pi/3$ as it is shown in Figure 11. Now we are
ready to construct the node tile (see Figure 12).

b)$\pi/6$$\pi/3$a)

Figure 11: Bending of basic channels.

$W$$O$$P$$Q$$R$$B$$Y$$X$$A$$Z$$C$$c$$c$$c$$c$Left channelRight channelBottom
channelNode area$U$$V$

Figure 12: The node tile. The disks shown in red and blue are not parts of the
gadgets, the disks shown in magenta are used to fill space. The point $P$ is
the center of the tile.

  * •

We construct the node area formed by an equilateral triangle as it is shown in
Figure 10 (a).

  * •

We attach three basic channels to the node area as it is shown in Figure 10
(a); the channels are called _left_ , _right_ and _bottom_ , respectively, as
it is shown in Figure 12.

  * •

To construct the left (right, respectively) channel, we use a basic channel
with $\pi/6$ bend as is it is shown in Figure 11 (a). Notice that
$|PR|=4+\sqrt{3}$, where $R$ is the point in the channel after the bend. To
make the distances integer, we insert $2-\sqrt{3}$ gap in the basic channel
(see Figure 7 (a)). Then we insert two gaps of length $1/2$ to adjust
distances.

  * •

To construct the bottom channel, we bend the basic channel as it is it shown
in Figure 11 (b) to adjust the direction. Then we make the level adjustment
(see Figure 6 (b)). Note that $|PQ|=2\sqrt{3}+11$, where $Q$ is the point in
the channel after the bending and level adjustment. We introduce $4-2\sqrt{3}$
gap and then we add $6$ gaps of length $1/2$ between parts of the basic
channel to adjust distances and compensate that we can place more disks in
bends that in a straight basic channel.

  * •

The remaining space around the node area and channel is filled by disks as it
is shown in Figure 12.

The disks with their centers in $A$, $B$ and $C$ are called _poles_ of the
node tile.

The properties of the node tile which follow from 3, 4, and 6 are summarized
in the next lemma.

######  Lemma 4.

At most $(c-1)/2$ disks can be placed inside each channel and it is possible
to place $(c-1)/2$ disks. Also at most one disks with its center inside the
node area can be placed but it is possible to place the disk with its center
in $O$. Furthermore, the following holds.

  * •

Only disks inside the channels and the node area can be added.

  * •

If there is a disk whose center is properly inside the node area, then at most
$(c-1)/2$ disks can be placed in the left (right and bottom, respectively)
channel. If exactly $(c-1)/2$ disks are placed, then one of the disks has its
center in $X$ ($Y$ and $Z$, respectively).

  * •

If there is a disk with its center in $U$ ($V$ and $W$, respectively), then at
most $(c-1)/2$ disks (including the disk with its center in $U$ ($V$ and $W$,
respectively)) can be placed in the left (right and bottom, respectively)
channel, and if exactly $(c-1)/2$ disks are placed, then they are completely
inside the tile and it is impossible to place an additional disk having its
center inside the tile except disks that may be placed in other channels.

The construction of the node tile limits the choice of the constant $c$.

######  Observation 7.

The (straight, twisted, parity adjustment) channel, bend, node tiles can be
constructed for $c=47$.

###### Proof.

To construct the bottom channel in the node tile, we insert 7 gaps and a gap
may be inserted between basic channels of size at least 2 (see Figure 7 (a)
and 4). Then taking into account the distance between the points $O$ and $Q$
in Figure 12 and the number of gaps, we obtain that the bottom channel can be
constructed for $c=47$. As for constructing the left and right channels in the
node tile, we insert 3 gaps, we also have that they can be constructed for
$c=47$. By similar arguments, we also can construct the (straight, twisted,
parity adjustment) channel tile and the bend tile if $c=47$. ∎

### Proof of Theorem 1: The final step.

Now we have all ingredients to finish the hardness proof for Disk Appending.

Recall that we prove $\operatorname{NP}$-hardness by reducing from Independent
Set on planar cubic graphs [16, 25]. Let $(G,k)$ be an instance of Independent
Set where $G$ is an $n$-vertex planar cubic graph. Let us remind the initial
steps. By Proposition 2, we can construct a rectilinear embedding of $G$ with
area $\mathcal{O}(n^{2})$ in linear time. Further, we modify the embedding to
ensure that the length of every segment of a broken line representing an edge
in the embedding is at least three. As we already pointed, this can be done by
replacing every vertex or bend point $(x,y)$ of the embedding by the point
$(3x,3y)$ and the corresponding adjustment of the segments in the broken
lines. After this modification we still have an embedding with
$\mathcal{O}(n^{2})$ area. We assume that $R=[0,a]\times[0,b]$ for
$a,b\in\mathbb{N}$ is the minimum area rectangle containing the embedding
(note that $a,b>0$ because $G$ is cubic and cannot be embedded on the line).

We define $a^{\prime}=2ca$ and $b^{\prime}=2cb$, where $c=47$, and set
$R^{\prime}=[0,a^{\prime}]\times[0,b^{\prime}]$ defining the rectangle in the
output instance of Disk Appending. Then we put tiles into $R^{\prime}$ as
follows.

  * •

For every $(x,y)\in R$ such that the point $(x,y)$ is not a point of the
embedding of $G$, put a copy of the filler tile whose bottom left corner in
$(2cx,2cy)$.

  * •

For every $(x,y)\in R$ such that $(x,y)$ is a vertex of $G$ in the embedding,
put a copy of the node tile with the bottom left corner in $(2cx,2cy)$. We
rotate the node tile in such a way that the directions of the left, right and
bottom channels coincide with the directions of line segments of the embedding
with the endpoints in $(x,y)$; note that because the distance between any two
vertices in the embedding is at least three, the poles of distinct node tiles
do not interfere with each other.

  * •

For every $(x,y)\in R$ such that $(x,y)$ is a bend node in the embedding of an
edge, put a copy of the bend tile with the bottom left corner in $(2cx,2cy)$.
We rotate the tile in such a way that the directions of the left and bottom
channels coincide with the directions of line segments of the embedding with
the endpoints in $(x,y)$. Again we note that because the distance between a
bend point and another bend point or a vertex in the embedding is at least
three, there is no intersections between the poles of constructed tiles.

  * •

For every edge $e\in E(G)$, let $P_{e}$ be the set of internal non-bending
integer points of the embedding of $e$.

We select an arbitrary point $(x,y)\in P_{e}$ and insert a copy $T$ of the
parity adjustment channel tile with the bottom left corner in $(2cx,2cy)$. We
rotate $T$ in such a way that the direction of its channel coincides with the
direction of line segments of the embedding containing $(x,y)$. Notice that
because the length of every segment of a broken line representing an edge in
the embedding is at least three, $T$ may be adjacent to at most one already
placed tile $T^{\prime}$ whose pole intersects $T$. If such a pole of
$T^{\prime}$ has the same center as the corresponding pole of $T$, we unify
these disks. Otherwise, if the poles have distinct centers, we reflect $T$ to
ensure that the poles have the same centers and unify them.

For every other point $(x,y)\in P_{e}$, we insert a tile $T$ which is a copy
of either straight or twisted channel tile. We rotate $T$ to have the same
direction of the channel as the direction of the segment of the line
containing $(x,y)$ in the embedding. Observe that $T$ can have ether one or
two adjacent already placed tiles whose poles intersect $T$. If $T$ is not
adjacent to any such a tile, we select $T$ be a copy of the straight tile. If
$T$ is adjacent to one such a tile $T^{\prime}$, then we select $T$ be a copy
of the straight channel tile. Then we ether identify the interfering poles of
$T$ and $T^{\prime}$ if they have the same centers or reflect $T$ and identify
the poles afterwards. Suppose that $T$ is adjacent to two tiles $T^{\prime}$
and $T^{\prime\prime}$ with interfering poles. If the poles are on the same
side with respect to the channel, then we choose $T$ be a copy of the straight
channel tile. Then we ether identify the interfering poles of $T$ and
$T^{\prime}$ if they have the same centers or reflect $T$ and identify the
poles afterwards. Otherwise, we select $T$ be a copy of the twisted channel
tile and reflect $T$ if necessary to identify the poles.

The construction of the tiles for $(x,y)\in P_{e}$ is shown in Figure 13 (a).

a)$(c-1)/2$$c$$c$$c-2$$c-1$$c-2$$c$$c$$(c-1)/2$$c-1$b)$T_{u}$$T_{v}$Node
tilesBend tilesStraight tilesTwisted tilesParity adjustment tile

Figure 13: The construction of tiles for an edge and placement of tiles. The
node areas and channels are shown in red and the poles are shown by black
bullets. The placement of disk in tiles associated with the edge is shown in
blue and the disk that may be placed in the center of $T_{u}$ is shown in
magenta.

We define $\mathcal{P}$ be the set of all disks in the tiles (taking into
account identifications of poles). By the construction, $\mathcal{P}$ is a
packing of disks inside $R^{\prime}$.

Clearly, we have $n$ node tiles. Denote by $n_{b}$ the number of bend tiles,
by $n_{p}=|E(G)|$ the number of parity adjustment channel tiles, and by
$n_{c}$ the number of straight and twisted channel tiles. We set
$k^{\prime}=k+3n(c-1)/2+(c-2)n_{b}+(c-1)n_{p}+cn_{c}$.

We clam that $G$ has an independent set of size of size at least $k$ if and
only if $(R^{\prime},\mathcal{P},k^{\prime})$ is a yes-instance of Disk
Appending.

For every edge $e$ of $G$, denote by $n_{b}^{e}$ the number of bend tiles and
by $n_{c}^{e}$ the number of straight and twisted tiles in the set of tiles
corresponding to the embedding of $e$.

For the forward direction, assume that $G$ has an independent set $S$ of size
$k$. For every vertex $v\in S$, we consider the node tile $T_{v}$
corresponding to $v$ and place a disk having its center in the center of the
tile (point $O$ in Figure 12). Consider an edge $e=uv$ of $G$. Because $S$ is
an independent set $u\notin S$ or $v\notin S$. Assume without loss of
generality that $v\notin S$ and it may happen that $u\in S$. Then we can
insert $(c-1)/2$ disks in the channels of $T_{v}$ and $T_{u}$ corresponding to
$e$ by Lemma 4, $c-2$ disks per each bend tile by Lemma 3, $c-1$ disks in the
unique parity adjustment channel tile by Lemma 2, and $c$ disks per each
straight or twisted channel tile by Lemma 1 as it is shown in Figure 13 (b)
(we associate a pole disk shared by tiles with the first tile containing it
along $e$ if moving from $u$ to $v$). Thus, we placed
$2(c-1)/2+(c-2)n_{b}^{e}+(c-1)+cn_{c}^{e}$ disks. Summarizing over all edges
and taking into account the disks corresponding to the vertices of $S$, we
obtain that we placed $k^{\prime}=k+3n(c-1)/2+(c-2)n_{b}+(c-1)n_{p}+cn_{c}$
disks.

For the opposite direction, assume that at least $k^{\prime}$ disk can be
placed in $R^{\prime}$ to complement the packing $\mathcal{P}^{\prime}$. By
Lemmas 1 and 4, new disks can be only placed inside channels and node areas of
the tiles. Let $\mathcal{S}$ be a packing of $k^{\prime}$ disks in
$R^{\prime}$ disjoint with the disks of $\mathcal{P}$ such that the number of
disks in $\mathcal{S}$ whose centers are properly inside of the node areas of
node tiles is minimum.

Consider an edge $e=uv$ of $G$. By Lemmas 1 and 4, at most
$2(c-1)/2+(c-2)n_{b}^{e}+(c-1)+cn_{c}^{e}$ disks can be placed in the channels
of $T_{v}$ and $T_{u}$ corresponding to $e$, the bend tiles, the unique parity
adjustment channel tile and all straight or twisted channel tiles (see Figure
13 (b) for an illustration). Moreover, for each $w\in V(G)$, at most one disk
of $\mathcal{S}$ can have its center properly inside of the node area of
$T_{w}$. Summarizing over all edges, we conclude that at least $k$ disks of
$\mathcal{S}$ have their centers in the node areas of node tiles and for every
$w\in V(G)$, at most one of these disks has its center inside of the node area
of $T_{w}$.

Suppose that there are two disks in $\mathcal{S}$ such that their centers are
inside of the node areas of $T_{u}$ and $T_{v}$. Then by Lemmas 1 and 4, we
conclude that at most $2(c-1)/2+(c-2)n_{b}^{e}+(c-1)+cn_{c}^{e}-1$ disks are
placed in the channels of $T_{v}$ and $T_{u}$ corresponding to $e$ and other
tiles associated with $e$. Then by 6, we can relocate the disk with its center
in the node area of $T_{v}$ and move it to the channel of $T_{v}$ associated
with $e$. Then we still would be able to place
$2(c-1)/2+(c-2)n_{b}^{e}+(c-1)+cn_{c}^{e}$ disks by the same arguments as in
the proof for the forward direction. This means that the relocation does not
decrease the number of added disks. However, this contradicts our assumption
about the choice of $\mathcal{S}$ as we decrease the number of disks with
centers that are properly inside of the node areas of node tiles. Hence, for
every $e=uv$, there is no disk with its center in the node area of $T_{u}$ or
$T_{v}$.

Let $S\subseteq V(G)$ be the set of all vertices $w$ such that the node tile
$T_{w}$ has a disk of $\mathcal{S}$ with its center inside of the node area.
We conclude that $S$ is an independent set $G$ of size at least $k$. This
completes the proof of our claim.

The number of disks in each tile is at most $c^{2}$. This implies that each
tile can be constructed in constant time. The area of the rectilinear
embedding of $G$ constructed by the algorithm from Proposition 2 is
$\mathcal{O}(n^{2})$. Therefore, we construct $\mathcal{O}(n^{2})$ tiles.
Since the algorithm from Proposition 2 is polynomial, we conclude that the
instance $(R^{\prime},\mathcal{P},k^{\prime})$ of Disk Appending is
constructed in polynomial time. This completes the proof Theorem 1.

We proved Theorem 1 assuming the real RAM model. In particular, to construct
tiles we used disks with algebraic coordinates of their centers. However, we
can observe that our construction is robust to allow rounding of coordinates.
More precisely, we can choose a sufficiently small constant $\delta>0$ and use
rational parameters $\hat{h}$ and $\hat{h}^{\prime}$ such that
$2+\sqrt{3}=h<\hat{h}\leq h+\delta$ and
$2\sqrt{3}=h^{\prime}<\hat{h}^{\prime}\leq h^{\prime}+\delta$ in the
construction of the basic channels (see Figure 4) and the node areas (see
Figure 10) instead of $h$ and $h^{\prime}$, respectively. This observation
allows to obtain the following corollary.

######  Corollary 1.

Disk Appending is $\operatorname{NP}$-hard when constrained to the instances
$(R,\mathcal{P},k)$ where the centers all disks in $\mathcal{P}$ have rational
coordinates. Furthermore, the problem remains $\operatorname{NP}$-hard when it
is only allowed to add new disks to $\mathcal{P}$ with rational coordinates of
their centers.

In Disk Repacking, the area of the packing of disks is bounded by a rectangle
$R$. However, we can consider different types of boundaries. In particular,
the boundary can be defined by disks in a given packing. Then we can obtain
the following corollary.

######  Corollary 2.

Given a rectangle $R=[0,2a]\times[0,2b]$ for integers $a,b>0$, a packing
$\mathcal{P}$ of disks with their centers inside $R$ such that (i) for every
$i\in\\{0,\ldots,a\\}$, the disks with centers $(2i,0)$ and $(2i,2b)$ are in
$\mathcal{P}$ and (ii) for every $j\in\\{0,\ldots,b\\}$, the disks with
centers $(0,2j)$ and $(2a,2j)$ are in $\mathcal{P}$, and an integer $k\geq 0$,
it is $\operatorname{NP}$-hard to decide whether $k$ disks with their centers
in $R$ can be added to $\mathcal{P}$ to form a packing. Moreover, the problem
remains hard if $a=b$.

##  4 An FPT algorithm for Disk Repacking

In this section, we prove that Disk Repacking is $\operatorname{FPT}$ when
parameterized by $k+h$. See 2

### Proof of Theorem 2: Overview.

On a high-level, the idea behind the algorithm is as follows. We first perform
a greedy procedure to ensure that all “free” areas to place disks can be
intersected by a set $\cal H$ of at most $k$ disks. Afterwards, we make use of
a coloring function of $\cal P$ with the objective to color all disks in $\cal
P$ that are repacked by a solution (if one exists) blue, and all disks in
$\cal P$ that “closely surround” them by red. We need to ensure that, while
relying on the initial greedy procedure, it would suffice to correctly color
only $\mathcal{O}(h+k)$ disks. Indeed, this gives rise to the usage of a
universal set, which is a “small” family of coloring functions ensured to
contain, if there exists a solution, at least one coloring function that
correctly colors all $\mathcal{O}(h+k)$ disks we care about.

Considering some coloring function (which expected to be “compatible” with
some solution), we identify “slots” and, more generally, “containers” in its
coloring pattern. In simple words, a slot is just a disk in $R$ that does not
intersect any red disk (from $\cal P$), and a container is a maximally
connected region consisting of slots. We are able to prove that, if the
coloring is compatible with some solution, then, for any container, either all
or none of the disks in ${\cal P}$ that are contained in the container are
repacked. This gives rise to a reduction from the problem of finding a
solution compatible with a given coloring to the Knapsack problem (more
precisely, an extended version of it), where each container corresponds to an
item whose weight is the number of disks in ${\cal P}$ that it contains, and
whose value is the number of disks that can be packed within it.

To execute the reduction described above, we need to be able to compute the
value of each container. For this purpose, we first prove that a container can
be “described” by only $\mathcal{O}(h+k)$ many disks from ${\cal P}\cup{\cal
H}$; more precisely, we show that each container is the union of disks
contained in $R$ that intersect at least one out of $\mathcal{O}(h+k)$ disks
in ${\cal P}\cup{\cal H}$, from which we subtract the union of some other
$\mathcal{O}(h+k)$ disks from ${\cal P}$. Having this at hand, to compute the
value of a container, we first “guess”, for each disk packed by a
(hypothetical) optimal packing of disks in the container, a disk from ${\cal
P}\cup{\cal H}$ contained in the container (making use of its description)
with whom it intersects. After that, we seek the corresponding optimal packing
by making use of a system of polynomial equations (inequalities) of degree
$2$, $\mathcal{O}(h+k)$ variables, and $\mathcal{O}((h+k)^{2})$ equations.

### Proof of Theorem 2: Free areas.

To execute the plan above, we start with the task of handling the “free”
areas. For this, we have the following definition and immediate observation.

######  Definition 1 (Holes and Hole Cover).

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. The set of holes,
denoted by $\mathsf{Holes}$, is the set of all disks contained in $R$ that are
disjoint from all disks in $\cal P$. A set ${\cal H}$ of disks contained in
$R$ such that the set of holes of $({\cal P}\cup{\cal H},R,h,k)$ is empty is
called a hole cover.

Figure 14: An instance $(\mathcal{P},R,h=2,k=7)$ of Disk Repacking. The disks
in $\mathcal{P}$ are colored black. The disks in some hole cover $\mathcal{H}$
are colored green (using dashed lines).

Figure 15: A solution $\mathcal{P}^{*}$ for the instance on the left. The
disks in $\mathcal{P}^{*}\setminus\mathcal{P}$ are drawn in purple (using
dashed lines).The set of $(\mathcal{H},\mathcal{P}^{*})$-critical disks is the
set of green disks from the figure on the left and the purple disks from the
figure on the right.

Figure 16: With respect to the instance and solution described in Figures 15
and 15, the disks $(\cal{H},\cal{P}^{*})$-forced to be blue are colored blue,
and the disks $(\mathcal{H},\mathcal{P}^{*})$-forced to be red are colored
red. Note that each of the disks colored black can be colored either blue or
red by an $(\mathcal{H},\mathcal{P}^{*})$-compatible coloring.

Figure 17: Consider an $(\mathcal{H},\mathcal{P}^{*})$-compatible coloring
that colors blue all of the disks colored black in Figure 17. Then, we have
four $c$-Containers, which roughly correspond to the areas colored by grey.

######  Observation 8.

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. Let ${\cal H}$ be a
hole cover. Then, every disk contained in $R$ intersects at least one disk in
${\cal P}\cup{\cal H}$.

Next, we present a definition and a lemma that will allow us to assume that we
have a hole cover of small size at hand.

######  Definition 2 (Dense instance).

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. We say that the
instance is dense if it has a hole cover of size smaller than $k$.

######  Lemma 5.

There exists a polynomial-time algorithm that, given an instance $({\cal
P},R,h,k)$ of Disk Repacking, either correctly determines that $({\cal
P},R,h,k)$ is a yes-instance or correctly determines that $({\cal P},R,h,k)$
is dense and returns a hole cover of size smaller than $k$.

###### Proof.

We perform a simple greedy procedure. Initially, ${\cal H}=\emptyset$. Then,
as long as there exists a disk $D$ contained in $R$ that is disjoint from all
disks in ${\cal P}\cup{\cal H}$, we add such a disk $D$ to $\cal H$. The test
for the existence of such a $D$ can be performed by using a system of
polynomial equations of degree $2$ with two variables denoting the $x$\- and
$y$-coordinates of the center of $D$. For each disk in ${\cal P}\cup{\cal H}$,
we have an equation enforcing that the distance between its center and the
center of $D$ is at least $2$, and additionally we have two linear equations
to enforce that $D$ is contained in $R$. By Proposition 1, testing whether
this system has a solution (which corresponds to the sought disk $D$) can be
done is polynomial time. Once the process terminates, the algorithm checks
whether $|{\cal H}|\geq k$. If the answer is positive, then adding ${\cal H}$
(or, more precisely, any subset of size $k$ of it) to $\cal P$ is a solution,
and so the algorithm answers yes, and otherwise the instance is dense and the
algorithm returns $\cal H$ (which witnesses that). ∎

In the two following definitions, we identify the coloring functions that will
be useful.

######  Definition 3 ($({\cal H},{\cal P}^{*})$-Critical Disks).

Let $({\cal P},R,h,k)$ be a yes-instance of Disk Repacking. Let ${\cal H}$ be
a hole cover. Let ${\cal P}^{*}$ be a solution to $({\cal P},R,h,k)$. The set
of $({\cal H},{\cal P}^{*})$-critical disks, denoted by $\mathsf{Crit}_{{\cal
H},{\cal P}^{*}}$, is $({\cal P}^{*}\setminus{\cal P})\cup{\cal H}$.

######  Definition 4 ($({\cal H},{\cal P}^{*})$-Compatible Colorings).

Let $({\cal P},R,h,k)$ be a yes-instance of Disk Repacking. Let ${\cal H}$ be
a hole cover. Let ${\cal P}^{*}$ be a solution to $({\cal P},R,h,k)$. Let
$c:{\cal P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$. We say that $c$ is
$({\cal H},{\cal P}^{*})$-compatible if:

  1. 1.

For every $D\in{\cal P}\setminus{\cal P}^{*}$, we have that
$c(D)=\mathsf{blue}$. We say that the disks in ${\cal P}\setminus{\cal P}^{*}$
are $({\cal H},{\cal P}^{*})$-forced to be blue.

  2. 2.

For every $D\in{\cal P}\cap{\cal P}^{*}$ whose center is at distance at most 4
from the center of some disk in $\mathsf{Crit}_{{\cal H},{\cal P}^{*}}$, we
have that $c(D)=\mathsf{red}$. We say that the disks in ${\cal P}\cap{\cal
P}^{*}$ whose center is at distance at most 4 from the center of some disk in
$\mathsf{Crit}_{{\cal H},{\cal P}^{*}}$ are $({\cal H},{\cal P}^{*})$-forced
to be red.

We proceed to show that the number of disks in $\cal P$ that should be colored
“correctly” is only $\mathcal{O}(h+k)$. This is done using the following easy
observation, in the following lemma.

######  Observation 9.

The number of pairwise disjoint disks inside a circle of radius $r$ is at most
$\pi r^{2}$.

######  Lemma 6.

Let $({\cal P},R,h,k)$ be a dense yes-instance of Disk Repacking. Let ${\cal
H}$ be a hole cover of size smaller than $k$. Let ${\cal P}^{*}$ be a solution
to $({\cal P},R,h,k)$. Then, the number of disks $({\cal H},{\cal
P}^{*})$-forced to be either blue or red is altogether bounded by
$\mathcal{O}(h+k)$.

###### Proof.

Because ${\cal P}^{*}$ is a solution and $|{\cal H}|<k$, we have that $|{\cal
P}\setminus{\cal P}^{*}|\leq h$. So, at most $h$ disks are $({\cal H},{\cal
P}^{*})$-forced to be blue. Further, $|\mathsf{Crit}_{{\cal H},{\cal
P}^{*}}|=|({\cal P}^{*}\setminus{\cal P})\cup{\cal H}|<h+2k$. Observe that
every disk in ${\cal P}\cap{\cal P}^{*}$ whose center is at distance at most 4
from the center of some disk in $\mathsf{Crit}_{{\cal H},{\cal P}^{*}}$ is
contained inside a circle of radius $5$ whose center is the center of some
disk in $\mathsf{Crit}_{{\cal H},{\cal P}^{*}}$. So, due to 9 and since the
disks in ${\cal P}\cap{\cal P}^{*}$ are pairwise disjoint, there exist at most
$\pi\cdot 5^{2}\cdot(h+2k)=\mathcal{O}(h+k)$ disks in ${\cal P}\cap{\cal
P}^{*}$ whose center is at distance at most 4 from the center of some disk in
$\mathsf{Crit}_{{\cal H},{\cal P}^{*}}$. In particular, this means that at
most $\mathcal{O}(h+k)$ disks are $({\cal H},{\cal P}^{*})$-forced to be red.
This completes the proof. ∎

### Proof of Theorem 2: Values of containers.

Next, we present the definition of slots and containers, in which we will aim
to (re)pack disks. The definition is followed by an observation and a lemma,
which, in particular, state that if we try to repack at least one disk in a
container, we can just repack all disks in that container.

######  Definition 5 ($c$-Slots and $c$-Containers).

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. Let $c:{\cal
P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$. The set of $c$-slots, denoted
by $\mathsf{Slots}_{c}$, is the set of disks contained in $R$ that are
disjoint from all disks in $\cal P$ that are colored red by $c$. The set of
$c$-containers, denoted by $\mathsf{Containers}_{c}$, is the set of maximally
connected regions in the union of all disks in $\mathsf{Slots}_{c}$.

######  Observation 10.

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. Let $c:{\cal
P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$. Then, the regions in
$\mathsf{Containers}_{c}$ are pairwise disjoint.

######  Lemma 7.

Let $({\cal P},R,h,k)$ be a yes-instance of Disk Repacking. Let ${\cal H}$ be
a hole cover. Let ${\cal P}^{*}$ be a solution to $({\cal P},R,h,k)$. Let
$c:{\cal P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$ be $({\cal H},{\cal
P}^{*})$-compatible. Then, for every region $X\in\mathsf{Containers}_{c}$,
either all disks in ${\cal P}$ contained in $X$ belong to ${\cal
P}\setminus{\cal P}^{*}$ or none of the disks in ${\cal P}\cup{\cal P}^{*}$
contained in $X$ belongs to $({\cal P}\setminus{\cal P}^{*})\cup({\cal
P}^{*}\setminus{\cal P})$.

###### Proof.

Targeting a contradiction, suppose that there exists a disk $D$ contained in
$X$ that belongs to $({\cal P}\setminus{\cal P}^{*})\cup({\cal
P}^{*}\setminus{\cal P})$ and a disk $D^{\prime}$ contained in $X$ that
belongs to ${\cal P}\cap{\cal P}^{*}$. Let $\gamma$ be a curve connecting the
centers of these disks that lies entirely inside $X$. By the definition of a
$c$-container and due to 8, every point of this curve contained in a disk that
belongs to $X$ and intersects a disk in $\cal P$ colored blue by $c$ or a disk
in $\cal H$. So, there must exist a point on $\gamma$ that is the center of a
disk $D^{*}$ that intersects both a disk $A$ contained in $X$ that belongs to
$({\cal P}\setminus{\cal P}^{*})\cup{\cal H}$ and a disk $A^{\prime}$
contained in $X$ that belongs to ${\cal P}\cap{\cal P}^{*}$. From the
definition of a $c$-container, $A^{\prime}$ is colored blue by $c$. Moreover,
note that the center of $A^{\prime}$ is at distance at most $4$ from the
center of $A$, since each of the centers of $A$ and $A^{\prime}$ is at
distance at most 2 from the center of $D^{*}$. However, since $c$ is $({\cal
H},{\cal P}^{*})$-compatible, $A^{\prime}$ is $({\cal H},{\cal P}^{*})$-forced
to be red and hence it is colored red by $c$. Since $c$ cannot color a disk
both blue and red, we have reached a contradiction. This completes the proof.
∎

We proceed to define the weight and value of a $c$-container, which will be
required for the reduction of our problem to Knapsack.

######  Definition 6 (Weight, Validity and Value of Containers).

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. Let $c:{\cal
P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$. Let
$X\in\mathsf{Containers}_{c}$. The weight of $X$ is the number of disks in
$\cal P$ that it contains. We say that $X$ is valid if its weight is at most
$h$. The value of $X$ is the maximum number of disks that can be packed inside
$X$.

The following is a corollary of Lemma 7.

######  Corollary 3.

Let $({\cal P},R,h,k)$ be a yes-instance of Disk Repacking. Let ${\cal P}^{*}$
be a solution to $({\cal P},R,h,k)$. Let $c:{\cal
P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$ be
$(\cal{H},\cal{P}^{*})$-compatible. Then, every disk in $({\cal
P}\setminus{\cal P}^{*})\cup({\cal P}^{*}\setminus{\cal P})$ is a $c$-slot,
and it is contained in a valid $c$-container.

Now, we define a way in which we can “easily” describe a container, and then
prove that this way can be encoded compactly.

######  Definition 7 (Descriptions of Containers).

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. Let ${\cal H}$ be a
hole cover. Let $c:{\cal P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$. An
$\cal H$-description (or, for short, description) of a region
$X\in\mathsf{Containers}_{c}$ is a pair $({\cal D}_{1},{\cal D}_{2})$ of a
subset ${\cal D}_{1}\subseteq{\cal P}\cup{\cal H}$ and a minimal subset ${\cal
D}_{2}\subseteq{\cal P}$ such that $X$ equals the set of all points in $R$ at
distance less than $2$ from at least one disk in ${\cal D}_{1}$ and at least
$2$ from all disks in ${\cal D}_{2}$.

######  Lemma 8.

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. Let ${\cal H}$ be a
hole cover. Let $c:{\cal P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$. Let
$X\in\mathsf{Containers}_{c}$. Then, $X$ has at least one description $({\cal
D}_{1},{\cal D}_{2})$. Moreover, every description $({\cal D}_{1},{\cal
D}_{2})$ of $X$ satisfies $|{\cal D}_{1}|+|{\cal
D}_{2}|=\mathcal{O}(h^{\prime}+k^{\prime})$ where $h^{\prime}$ is the weight
of $X$, and $k^{\prime}$ is the number of disks in $\cal H$ contained in $X$.

###### Proof.

By 8, every $c$-slot intersects at least one disk in $\\{D\in{\cal
P}:c(D)=\mathsf{blue}\\}\cup{\cal H}$ and is disjoint from all disks in
$\\{D\in{\cal P}:c(D)=\mathsf{red}\\}$. Further, every point in every disk in
$\\{D\in{\cal P}:c(D)=\mathsf{blue}\\}\cup{\cal H}$ is contained in a
$c$-slot. So, it is immediate that $X$ has a description $({\cal D}_{1},{\cal
D}_{2})$, and that $|{\cal D}_{1}|=\mathcal{O}(h^{\prime}+k^{\prime})$. Due to
9 and since the disks in ${\cal P}\cup{\cal H}$ are pairwise disjoint, any
circle of radius $5$ whose center is a center of some disk in $\\{D\in{\cal
P}:c(D)=\mathsf{blue}\\}\cup{\cal H}$ can contain inside at most $\pi\cdot
5^{2}$ disks from $\\{D\in{\cal P}:c(D)=\mathsf{red}\\}$. Due to the
minimality of ${\cal D}_{2}$ (which is a subset of $\\{D\in{\cal
P}:c(D)=\mathsf{red}\\}$), every disk in it must be contained inside a circle
of radius $5$ whose center is a center of some disk in $\\{D\in{\cal
P}:c(D)=\mathsf{blue}\\}\cup{\cal H}$. Hence, $|{\cal D}_{2}|\leq|{\cal
D}_{1}|\cdot\pi\cdot 5^{2}=\mathcal{O}(h^{\prime}+k^{\prime})$. ∎

Next, we use a description in order to efficiently compute the value of a
$c$-container.

######  Lemma 9.

There is an $(h+k)^{\mathcal{O}(h+k)}\cdot|I|^{\mathcal{O}(1)}$-time algorithm
that, given a dense instance $I=({\cal P},R,h,k)$ of Disk Repacking, a hole
cover ${\cal H}$ of size smaller than $k$, $c:{\cal
P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$ and a valid region $X$ with a
description $({\cal D}_{1},{\cal D}_{2})$, computes the value of $X$.

###### Proof.

Given $I=({\cal P},R,h,k),{\cal H},c,X$ and $({\cal D}_{1},{\cal D}_{2})$, the
algorithm works as follows. For $\ell=h+k,h+k-1,\ldots,1$, and for every
vector $(D_{1},D_{2},\ldots,D_{\ell})\in{\cal D}_{1}\times{\cal
D}_{1}\times\cdots\times{\cal D}_{1}$, it tests whether there exist $\ell$
disks $S_{1},S_{2},\ldots,S_{\ell}$ such that, for every
$i\in\\{1,2,\ldots,\ell\\}$, $S_{i}$ intersects $D_{i}$, is contained in $R$
and is disjoint from all disks in ${\cal D}_{2}$. The test is done by
constructing a system of polynomial equations of degree $2$ with $2\ell$
variables and $\ell\cdot(|{\cal D}_{2}|+2)$ equations as follows. For every
$i\in\\{1,2,\ldots,\ell\\}$, we have two variables, denoting the $x$\- and
$y$-coordinates of the center of $S_{i}$, one equation enforcing that the
distance between the center of $S_{i}$ and the center of $D_{i}$ is smaller
than $2$, $|{\cal D}_{2}|$ equations enforcing that the distance between the
center of $S_{i}$ and the center of each of the disks in ${\cal D}_{2}$ is at
least $2$, and two linear equations enforcing that $S_{i}$ is contained inside
$R$. If the answer is positive, then the algorithm returns that the value of
$X$ is $\ell$ and terminates; else, it proceeds to the next iteration. Observe
that, when $\ell=1$, the algorithm necessarily terminates (since $X$ contains
at least one $c$-slot).

The correctness of the algorithm is immediate from the definition of a
description and the exhaustive search that it performs. As for the running
time, first observe that, by Lemma 8 and since $X$ is valid and $|{\cal
H}|<k$, $|{\cal D}_{1}|+|{\cal D}_{2}|\leq\mathcal{O}(h+k)$. So, for a given
$\ell$, we have $|{\cal D}_{1}|^{\mathcal{O}(\ell)}=(h+k)^{\mathcal{O}(h+k)}$
choices of vectors. Now, consider the iteration corresponding to some $\ell$
and some vector. Then, we solve a system of polynomial equations of degree $2$
with $\mathcal{O}(h+k)$ variables and $\mathcal{O}((h+k)^{2})$ equations. By
Proposition 1, this can be done in time
$(h+k)^{\mathcal{O}(h+k)}\cdot|I|^{\mathcal{O}(1)}$. Thus, the algorithm
indeed runs in time $(h+k)^{\mathcal{O}(h+k)}\cdot|I|^{\mathcal{O}(1)}$. ∎

The following definition captures the set of all descriptions.

######  Definition 8 (Blueprint).

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. Let ${\cal H}$ be a
hole cover. Let $c:{\cal P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$. An
$({\cal H},c)$-blueprint is a collection of pairs of sets
$\mathsf{Blueprint}\subseteq 2^{{\cal P}\cup{\cal H}}\times 2^{\cal{P}}$,
where the first elements of the pair are pairwise-disjoint subsets of
$\cal{P}\cup\cal{H}$, such that each region in $\mathsf{Containers}_{c}$ has
exactly one description in $\mathsf{Blueprint}$, and every pair in
$\mathsf{Blueprint}$ is a description of a region in
$\mathsf{Containers}_{c}$.

Next, we show how to compute blueprints.

######  Lemma 10.

There exists a polynomial-time algorithm that, given an instance $({\cal
P},R,h,k)$ of Disk Repacking, a hole cover ${\cal H}$, and $c:{\cal
P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$, outputs an $({\cal
H},c)$-blueprint.

###### Proof.

We will perform a simple greedy procedure to identify, for each disk in
$\\{D\in{\cal P}:c(D)=\mathsf{blue}\\}\cup{\cal H}$, the description of the
region that contains it. Observe that every $c$-container contains at least
one disk in $\\{D\in{\cal P}:c(D)=\mathsf{blue}\\}\cup{\cal H}$ (due to 8 and
the definition of a $c$-container). So, if for every disk $D\in\\{D\in{\cal
P}:c(D)=\mathsf{blue}\\}\cup{\cal H}$ we will take exactly one description
$({\cal D}_{1},{\cal D}_{2})$ among the descriptions we identified such that
$D$ is contained in ${\cal D}_{1}$, we will obtain an $({\cal
H},c)$-blueprint.

To describe the greedy procedure, consider some $D\in\\{D\in{\cal
P}:c(D)=\mathsf{blue}\\}\cup{\cal H}$. Let us first show how to attain ${\cal
D}_{1}$. For this purpose, we initialize ${\cal D}_{1}=\\{D\\}$. Then, for
every pair of disks $A\in{\cal D}_{1}$ and $B\in(\\{D\in{\cal
P}:c(D)=\mathsf{blue}\\}\cup{\cal H})\setminus{\cal D}_{1}$, we test whether
there exists a pair of disks $C$ and $C^{\prime}$ that are contained in $R$,
intersect each other, are disjoint from all disks in $\\{D\in{\cal
P}:c(D)=\mathsf{red}\\}$, and such that $C$ intersects $A$ and $C^{\prime}$
intersects $B$. The test for the existence of such a $C$ is performed by using
a system of polynomial equations of degree $2$ with four variables denoting
the $x$\- and $y$-coordinates of the centers of $C$ and $C^{\prime}$. For each
disk in $\\{D\in{\cal P}:c(D)=\mathsf{red}\\}$, we have two equations
enforcing that the distances between its center and the centers of $C$ and
$C^{\prime}$ are each at least $2$. Additionally, we have three equations to
enforce that the distance between the centers of $C$ and $C^{\prime}$ is
smaller than $2$, the distance between the centers of $C$ and $A$ is smaller
than $2$, and the distance between the centers of $C^{\prime}$ and $B$ is
smaller than $2$, as well as four linear equations to enforce that $C$ and
$C^{\prime}$ are contained in $R$. By Proposition 1, testing whether this
system has a solution (which corresponds to the sought disks $C$ and
$C^{\prime}$) can be done is polynomial time. If the answer is positive, then
we add $B$ to ${\cal D}_{1}$. In case at least one pair $(A,B)$ resulted in
the addition of $B$ to ${\cal D}_{1}$, then we repeat the entire loop,
iterating again over all pairs $(A,B)$ (where the domain from which they are
taken is updated as a new disk was added to ${\cal D}_{1}$). Notice that we
can perform at most $|{\cal P}|$ repetitions, and that each repetition results
in at most $|{\cal P}\cup{\cal H}|^{2}$ many iterations, each taking
polynomial time. Hence, the procedure, so far, runs in polynomial time.

Now, let us show how to attain ${\cal D}_{2}$. For this purpose, we initialize
${\cal D}_{2}=\\{D\in{\cal P}:c(D)=\mathsf{red}\\}$. Now, for every
$A\in\\{D\in{\cal P}:c(D)=\mathsf{red}\\}$, we test whether there exists a
disk $C$ that is contained in $R$ and intersects both $A$ and at least one
disk in ${\cal D}_{1}$, and is disjoint from all disks in ${\cal
D}_{2}\setminus\\{A\\}$. The test can be performed by iterating over every
disk $B\in{\cal D}_{1}$, and using a system of polynomial equations of degree
$2$ with two variables denoting the $x$\- and $y$-coordinates of the center of
$C$. For each disk in ${\cal D}_{2}\setminus\\{A\\}$, we have an equation
enforcing that the distance between its center and the center of $C$ is at
least $2$, and additionally we have two equations to enforce that the distance
between the center of $C$ and each of the centers of $A$ and $B$ is smaller
than $2$, as well as two linear equations to enforce that $C$ is contained in
$R$. By Proposition 1, testing whether this system has a solution (which
corresponds to the sought disk $C$) can be done is polynomial time. If the
answer is positive, then we remove $A$ from ${\cal D}_{2}$. Notice that this
phase of the procedure also runs in polynomial time. Moreover, the correctness
of the entire procedure directly follows from the definitions of a
$c$-container and a description. ∎

We proceed to define the (extended version of the) Knapsack problem and the
instances of this problem that our reduction produces.

######  Definition 9 ((Extended) Knapsack).

In the (Extended) Knapsack problem, we are given a collection of $n$ items
$U$, where each item $u\in U$ has a weight $w(u)\in\mathbb{N}_{0}$ and a value
$v(u)\in\mathbb{N}_{0}$, and an integer $W\in\mathbb{N}_{0}$. The objective is
to find, for every $W^{\prime}\in\\{0,1,\ldots,W\\}$, the maximum
$V_{W^{\prime}}\in\mathbb{N}_{0}$ for which there exists a subset of items
$S\subseteq\\{1,2,\ldots,n\\}$ such that $\sum_{i\in S}w(u)\leq W^{\prime}$
and $\sum_{i\in S}v(u)\geq V_{W^{\prime}}$.

######  Definition 10 ($({\cal H},c)$-Knapsack instance).

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. Let ${\cal H}$ be a
hole cover. Let $c:{\cal P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$. The
$({\cal H},c)$-Knapsack instance is the instance $(U,w,v,W,V)$ of Knapsack
defined as follows: $U$ is the set of all valid regions in
$\mathsf{Containers}_{c}$; for each $X\in U$, $w(X)$ and $v(X)$ are the weight
and value of $X$ (see Definition 6); $W=h$; $V=h+k$.

######  Proposition 3 ([7]).

The (Extended) Knapsack problem is solvable in time $\mathcal{O}(|U|\cdot W)$.

We now to prove the correspondence between our problem when we restrict the
solution set to solutions compatible with a given coloring and the Knapsack
problem.

######  Lemma 11.

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. Let ${\cal H}$ be a
hole cover. Let $c:{\cal P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$. Then,
there exists a solution ${\cal P}^{*}$ to $({\cal P},R,h,k)$ such that $c$ is
compatible with ${\cal P}^{*}$ if and only if for the $({\cal H},c)$-Knapsack
instance $(U,w,v,W,V)$, there exists $W^{\prime}\in\\{0,1,\ldots,W\\}$ such
that $V_{W^{\prime}}\geq W^{\prime}+k$.

###### Proof.

In one direction, suppose that there exists a solution ${\cal P}^{*}$ to
$({\cal P},R,h,k)$ such that $c$ is compatible with ${\cal P}^{*}$. Let
$X_{1},X_{2},\ldots,X_{\ell}$ be the $c$-containers that contain at least one
disk from $({\cal P}\setminus{\cal P}^{*})\cup({\cal P}^{*}\setminus{\cal
P})$. By 10, these $c$-containers are pairwise disjoint, by Lemma 7 and since
$c$ is compatible with ${\cal P}^{*}$, all disks in ${\cal P}$ contained in
$X_{1}\cup X_{2}\cup\cdots\cup X_{\ell}$ belong to ${\cal P}\setminus{\cal
P}^{*}$, and by Corollary 3 and since $c$ is compatible with ${\cal P}^{*}$,
all disks in $({\cal P}\setminus{\cal P}^{*})\cup({\cal P}^{*}\setminus{\cal
P})$ are contained in $X_{1}\cup X_{2}\cup\cdots\cup X_{\ell}$ and all of
these $c$-containers are valid. So, because ${\cal P}^{*}$ can repack $h$
disks from $\cal P$, the total weight of these $c$-containers must be some
$W^{\prime}\in\\{0,1,\ldots,h\\}=\\{0,1,\ldots,W\\}$, and since ${\cal P}^{*}$
also packs $k$ additional disks, the total value of these $c$-containers must
be at least $W^{\prime}+k$ (to accommodate all of the repacked and $k$ newly
packed disks). Thus, $V_{W^{\prime}}\geq W^{\prime}+k$.

In the other direction, suppose that there exists
$W^{\prime}\in\\{0,1,\ldots,W\\}$ such that $V_{W^{\prime}}\geq W^{\prime}+k$.
This means that there exist $c$-containers $X_{1},X_{2},\ldots,X_{\ell}$ whose
total weight is $W^{\prime}\in\\{0,1,\ldots,h\\}$ and whose total value is at
least $W^{\prime}+k$. However, because these $c$-containers are pairwise
disjoint (by 10), this means that we can construct a solution ${\cal P}^{*}$
such that $c$ is compatible with ${\cal P}^{*}$ by repacking all the disks in
$\cal P$ that are contained in $X_{1},X_{2},\ldots,X_{\ell}$ (there are at
most $h$ such disks) and, additionally, inserting $k$ new disks, within
$X_{1},X_{2},\ldots,X_{\ell}$. This completes the proof. ∎

The following is a corollary of Lemmas 9 and 10.

######  Corollary 4.

There exists an $(h+k)^{\mathcal{O}(h+k)}\cdot|I|^{\mathcal{O}(1)}$-time
algorithm that, given a dense instance $I=({\cal P},R,h,k)$ of Disk Repacking,
a hole cover ${\cal H}$ of size smaller than $k$ and $c:{\cal
P}\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$, computes the $({\cal
H},c)$-Knapsack instance.

To compute coloring functions, we will use the following definition and
proposition.

######  Definition 11 ($(U,k)$-Universal Set).

For a universe $U$ and $k\in\mathbb{N}$, a $(U,k)$-universal set is a
collection $\cal C$ of functions
$f:U\rightarrow\\{\mathsf{blue},\mathsf{red}\\}$ such that for every pair of
disjoint sets $B,R\subseteq U$ whose union has size at most $k$, there exists
$c\in{\cal C}$ that colors all integers in $B$ blue and all integers in $R$
red.

######  Proposition 4 ([26]).

There exists an algorithm that, given a universe $U$ of size $n$ and
$k\in\mathbb{N}$, constructs a $(U,k)$-universal set of size
$2^{k+\mathcal{O}(\log^{2}k)}\log n$ in time
$2^{k+\mathcal{O}(\log^{2}k)}n\log n$.

Based on the definition of a universal set, we define the collection of
Knapsack instances relevant to our reduction.

######  Definition 12 ($({\cal H},{\cal C})$-Knapsack Collection).

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. Let ${\cal H}$ be a
hole cover. Let ${\cal C}$ be a $({\cal P},q(h+k))$-universal set, where $q$
is the constant hidden in the $\mathcal{O}$-notation in Lemma 6. Then, the
$({\cal H},{\cal C})$-Knapsack collection is the collection of Knapsack
instances that includes, for every $c\in{\cal C}$, the $({\cal H},c)$-Knapsack
instance.

The following is a corollary of Corollary 4.

######  Corollary 5.

There exists an $(h+k)^{\mathcal{O}(h+k)}\cdot|I|^{\mathcal{O}(1)}$-time
algorithm that, given a dense instance $I=({\cal P},R,h,k)$ of Disk Repacking,
a hole cover ${\cal H}$ of size smaller than $k$ and a $({\cal
P},q(h+k))$-universal set $\cal C$, computes the $({\cal H},{\cal
C})$-Knapsack collection.

Next, we prove the correspondence between our problem and the collection of
Knapsack instances we have just defined.

######  Lemma 12.

Let $({\cal P},R,h,k)$ be an instance of Disk Repacking. Let ${\cal H}$ be a
hole cover. Let ${\cal C}$ be a $({\cal P},q(h+k))$-universal set. Then,
$({\cal P},R,h,k)$ is a yes-instance of Disk Repacking if and only if the
$({\cal H},{\cal C})$-Knapsack collection contains an instance $(U,w,v,W,V)$
for which there exists $W^{\prime}\in\\{0,1,\ldots,W\\}$ such that
$V_{W^{\prime}}\geq W^{\prime}+k$.

###### Proof.

In one direction, suppose that $({\cal P},R,h,k)$ is a yes-instance. By the
definition of a $({\cal P},q(h+k))$-universal set and due to Lemma 6, there
exists $c\in{\cal C}$ that is compatible with ${\cal P}^{*}$. So, the $({\cal
H},c)$-Knapsack instance is contained in the $({\cal H},{\cal C})$-Knapsack
collection $(U,w,v,W,V)$, and by Lemma 11, for this instance there exists
$W^{\prime}\in\\{0,1,\ldots,W\\}$ such that $V_{W^{\prime}}\geq W^{\prime}+k$.

In the other direction, suppose that the $({\cal H},{\cal C})$-Knapsack
collection contains an instance $(U,w,v,W,V)$ for which there exists
$W^{\prime}\in\\{0,1,\ldots,W\\}$ such that $V_{W^{\prime}}\geq W^{\prime}+k$.
This instance is a $({\cal H},c)$-Knapsack instance for some $c\in{\cal C}$.
So, by Lemma 11, $({\cal P},R,h,k)$ is, in particular, a yes-instance of Disk
Repacking. ∎

### Proof of Theorem 2: Putting it all together.

We are now ready to make the final step of the proof of Theorem 2.

The algorithm works as follows. Given an instance $({\cal P},R,h,k)$ of Disk
Repacking, it calls the algorithm in Lemma 5 to either correctly determine
that $({\cal P},R,h,k)$ is a yes-instance or correctly determine that $({\cal
P},R,h,k)$ is dense and obtain a hole cover $\cal H$ of size smaller than $k$.
In the first case, the algorithm is done. In the second case, the algorithm
proceeds as follows. First, it calls the algorithm in Proposition 4 to obtain
a $({\cal P},q(h+k))$-universal set $\cal C$. Then, it calls the algorithm in
Corollary 5 to obtain the $({\cal H},{\cal C})$-Knapsack collection.
Afterwards, it uses the algorithm of Proposition 3 to determine whether the
$({\cal H},{\cal C})$-Knapsack collection contains an instance $(U,w,v,W,V)$
for which there exists $W^{\prime}\in\\{0,1,\ldots,W\\}$ such that
$V_{W^{\prime}}\geq W^{\prime}+k$.

The correctness of the algorithm follows from Lemma 12. The runtime bound of
$(h+k)^{\mathcal{O}(h+k)}\cdot|I|^{\mathcal{O}(1)}$ follows from the runtimes
bounds of the algorithms that the algorithm calls, stated in Lemma 5,
Proposition 4, Corollary 5, and Proposition 3.

This concludes the proof of Theorem 2.

##  5 Conclusion and open questions

We have shown in Theorem 1 that Disk Repacking problem is
$\operatorname{NP}$-hard even if $h=0$. On the other hand, by Theorem 2, Disk
Repacking is $\operatorname{FPT}$ when parameterized by $k$ and $h$. Both
theorems naturally lead to the question about parameterization by $k$ only.
The difficulty here is that even for adding one disk, one has to relocate many
disks. Already for $k=1$, we do not know, whether the problem is in
$\operatorname{P}$ or is $\operatorname{NP}$-hard.

Another natural question stemming from Theorem 2 is about kernelization of
Disk Repacking. Does Disk Repacking admit a polynomial kernel with parameters
$k$ and $h$? (We refer to books [9, 14] for an introduction to kernelization).

Finally, approximation of Disk Repacking is an interesting research direction.
In Theorem 3 we demonstrated that our $\operatorname{FPT}$ algorithm can be
used to construct an $\operatorname{FPT-AS}$ with respect to $h$ for Max Disk
Repacking. We leave open the question about polynomial approximation. Another
open question concerns the approximability of the minimum number of
relocations $h$ for a given $k$. Already for $k=1$ finding a good
approximation of $h$ is a challenging problem.

## References

  * [1] M. Abrahamsen, T. Miltzow, and N. Seiferth, Framework for er-completeness of two-dimensional packing problems, in 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2020, pp. 1014–1021.
  * [2] P. Ashok, S. Kolay, S. M. Meesum, and S. Saurabh, Parameterized complexity of strip packing and minimum volume packing, Theor. Comput. Sci., 661 (2017), pp. 56–64.
  * [3] N. Bansal and A. Khan, Improved approximation algorithm for two-dimensional bin packing, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, C. Chekuri, ed., SIAM, 2014, pp. 13–25.
  * [4] S. Basu, R. Pollack, and M.-F. Roy, Algorithms in Real Algebraic Geometry, Springer, Berlin, Heidelberg, 2009.
  * [5] I. Castillo, F. J. Kampas, and J. D. Pintér, Solving circle packing problems by global optimization: numerical results and industrial applications, European Journal of Operational Research, 191 (2008), pp. 786–802.
  * [6] H. I. Christensen, A. Khan, S. Pokutta, and P. Tetali, Approximation and online algorithms for multidimensional bin packing: A survey, Comput. Sci. Rev., 24 (2017), pp. 63–79.
  * [7] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd Edition, MIT Press, 2006.
  * [8] H. T. Croft, K. Falconer, and R. K. Guy, Unsolved problems in geometry: unsolved problems in intuitive mathematics, vol. 2, Springer Science & Business Media, 2012.
  * [9] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized Algorithms, Springer, 2015\.
  * [10] E. D. Demaine, S. P. Fekete, and R. J. Lang, Circle packing for origami design is hard, CoRR, abs/1008.1224 (2010).
  * [11] R. Diestel, Graph Theory, 4th Edition, vol. 173 of Graduate texts in mathematics, Springer, 2012.
  * [12] S. P. Fekete, S. Morr, and C. Scheffer, Split packing: Algorithms for packing circles with optimal worst-case density, Discret. Comput. Geom., 61 (2019), pp. 562–594.
  * [13] F. V. Fomin, P. A. Golovach, T. Inamdar, and M. Zehavi, (re)packing equal disks into rectangle, in 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, M. Bojanczyk, E. Merelli, and D. P. Woodruff, eds., vol. 229 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 60:1–60:17.
  * [14] F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi, Kernelization, Cambridge University Press, Cambridge, 2019.  Theory of parameterized preprocessing.
  * [15] W. Gálvez, F. Grandoni, S. Ingala, S. Heydrich, A. Khan, and A. Wiese, Approximating geometric knapsack via L-packings, ACM Trans. Algorithms, 17 (2021), pp. 33:1–33:67.
  * [16] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
  * [17] M. Goldberg, The packing of equal circles in a square, Mathematics Magazine, 43 (1970), pp. 24–30.
  * [18] R. Harren, K. Jansen, L. Prädel, and R. van Stee, A (5/3 + $\epsilon$)-approximation for strip packing, Comput. Geom., 47 (2014), pp. 248–267.
  * [19] D. S. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, J. ACM, 32 (1985), pp. 130–136.
  * [20] K. Jansen and M. Rau, Closing the gap for pseudo-polynomial strip packing, in 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, M. A. Bender, O. Svensson, and G. Herman, eds., vol. 144 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 62:1–62:14.
  * [21] J. Kepler, Strena seu de nive sexangula, Frankfurt: Godefrid Tampach, 1611.
  * [22] Y. Liu, A. Morgana, and B. Simeone, A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid, Discret. Appl. Math., 81 (1998), pp. 69–91.
  * [23] M. Locatelli and U. Raber, Packing equal circles in a square: a deterministic global optimization approach, Discrete Applied Mathematics, 122 (2002), pp. 139–166.
  * [24] C. D. Maranas, C. A. Floudas, and P. M. Pardalos, New results in the packing of equal circles in a square, Discrete Mathematics, 142 (1995), pp. 287–293.
  * [25] B. Mohar, Face covers and the genus problem for apex graphs, J. Comb. Theory, Ser. B, 82 (2001), pp. 102–117.
  * [26] M. Naor, L. J. Schulman, and A. Srinivasan, Splitters and near-optimal derandomization, in 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, 1995, pp. 182–191.
  * [27] K. J. Nurmela et al., More optimal packings of equal circles in a square, Discrete & Computational Geometry, 22 (1999), pp. 439–457.
  * [28] K. J. Nurmela and P. R. Östergård, Packing up to 50 equal circles in a square, Discrete & Computational Geometry, 18 (1997), pp. 111–120.
  * [29] J. Schaer, The densest packing of 9 circles in a square, Canadian Mathematical Bulletin, 8 (1965), pp. 273–277.
  * [30] E. Specht, The best known packings of equal circles in a square (up to N= 10000), 2015.
  * [31] P. G. Szabó, M. C. Markót, T. Csendes, E. Specht, L. G. Casado, and I. García, New approaches to circle packing in a square: with program codes, vol. 6, Springer Science & Business Media, 2007.
  * [32] L. F. Tóth, Lagerungen in der Ebene auf der Kugel und im Raum, Springer, 1953.