Triangles and quadrilaterals suffice

Abstract

We prove a conjecture proposed by Robert J. Lang over 20 years ago, stating that in a circle-packed origami design, any axial polygon with 5 or more sides can be reduced by properly adding a new circle. The proof is based on the structure of the medial axis of the region enclosed by the circles, and yields a concrete algorithm for finding the added circle. The result extends to configurations involving rivers.

1 Introduction

In computational origami design, the circle/river method provides a systematic approach to constructing uniaxial bases with prescribed flap lengths by representing each flap as a circle whose radius is proportional to the desired flap length, then packing these circles such that their centers lie in the given square and the circles do not overlap. A key step in this method involves filling each axial polygon—formed by connecting the centers of mutually tangent circles—with the crease pattern of a corresponding molecule. For triangular and quadrilateral axial polygons, simple geometric constructions are known for their associated molecules. However, for polygons of order five or higher, no comparable geometric construction exists; instead, one must resort to numerical algorithms to compute the patterns of the molecules. This computational dependency poses a barrier to purely geometric origami design.

Lang observed [Lang 03, pp. 364–366] that this difficulty could potentially be circumvented through a reduction process. By judiciously adding a new circle tangent to at least three existing circles in an $N$-gon with $N>4$, one might decompose the configuration into smaller polygons, ultimately reducing all axial polygons to triangles and quadrilaterals. If successful, this approach would enable the design of arbitrary circle-packed bases using only geometric constructions, without reliance on computational tools. In all cases examined by Lang, such a reduction was indeed possible—one could always find a circle whose addition ensures that the largest reduced polygon has at most $N-1$ sides. However, a rigorous proof that this reduction is always achievable remained an open problem.

The significance of this problem lies not in its practical utility—adding circles introduces additional flaps that may complicate the folding process—but rather in its theoretical implications for understanding the geometric structure of circle packings in origami design. The question touches on fundamental properties of tangent circle arrangements and their associated polygonal decompositions. Lang noted that while certain configurations admit circles whose addition preserves the polygon order, in all examined cases an alternative placement could be found that achieves the desired reduction. This observation suggested a deeper geometric principle at work.

In this paper, we prove that Lang’s conjecture holds in full generality:

Theorem 1.

For any $N$–gon of touching circles with $N>4$, it is always possible to add a circle touching at least three others so that the largest reduced polygon has, at most, $N-1$ sides.

Furthermore, we show that the result extends to configurations incorporating rivers, demonstrating the robustness of the underlying geometric principle.

Our proof rests on the notion of the medial axis of a plane domain, introduced by Blum [Blum 67] in the context of shape recognition, and on the rigorous structure theory of medial axes later developed by Choi, Choi, and Moon [Choi et al. 97]. The key observation is that the free region enclosed by the circles of an axial polygon has a medial axis which is a tree with exactly $N$ leaves, and that the internal vertices of this tree are precisely the centers of the circles that may be added to the configuration so as to touch at least three of its circles. This identification absorbs all the geometry of the problem at once, as Lang’s conjecture reduces to a purely combinatorial property of trees, which we isolate as an elementary tree lemma (Lemma 4), the only non-geometric ingredient of the proof.

The paper is organized as follows. Section 2 collects the necessary definitions and background. Section 3 proves Theorem 1, together with a quantitative consequence—at most $N-4$ added circles suffice to reduce an $N$-gon completely into triangles and quadrilaterals (Corollary 2.1). Section 4 turns the proof into an explicit procedure. The construction is fully algorithmic—all figures in this paper were generated by our implementation of it—and, since each added circle solves a classical Apollonius tangency problem, it is constructible with straightedge and compass, so the reduction stays within the purely geometric means whose pursuit motivated Lang’s question in the first place. Section 5 shows that the bound of $N-4$ added circles cannot be improved. Section 6 extends the result to polygons crossed by a river, and Section 7 to polygons crossed by any number of rivers.

2 Preliminaries

2.1 Polygons of touching circles

Throughout the paper, all indices of objects associated with an $N$-gon are understood cyclically with respect to $N$ (unless otherwise stated), so that $v_{N+1}=v_{1}$, $C_{0}=C_{N}$, and so on.

Definition 1.

Let $C_{1},\dots,C_{N}$ be a collection of circles, where $C_{i}$ is centered at $v_{i}$ and has radius $r_{i}>0$. We say that the circles form an $N$-gon of touching circles if

1. the centers $v_{1},\dots,v_{N}$, in this cyclic order, are the vertices of a simple polygon $P$;

2. $\lvert\overline{v_{i}v_{i+1}}\rvert=r_{i}+r_{i+1}$ for all $i$, that is, consecutive circles are externally tangent; and

3. $\lvert\overline{v_{i}v_{j}}\rvert>r_{i}+r_{j}$ for all non-consecutive pairs $i,j$, that is, all other pairs of circles are disjoint.

We write $D_{i}$ for the closed disk bounded by $C_{i}$, and $t_{i}\in\overline{v_{i}v_{i+1}}$ for the point of tangency of $C_{i}$ and $C_{i+1}$.

These configurations are exactly the axial polygons arising in the circle/river method, in the special case where no river is present (the case with rivers will be covered in Section 6). We emphasize that $P$ is not assumed to be convex. Condition (3) excludes the degenerate case in which two non-consecutive circles also touch; this loses no generality, since such a configuration is already subdivided by the tangency into two polygons of touching circles of order at most $N-1$ each, and it suffices to apply Theorem 1 to a sub-polygon of order greater than four.

Definition 1 determines how the disks sit inside the polygon.

Lemma 1.

In an $N$-gon of touching circles, each edge $\overline{v_{i}v_{i+1}}$ of $P$ is covered by $D_{i}\cup D_{i+1}$; moreover, $D_{i}$ contains no vertex of $P$ other than $v_{i}$ and meets no edge of $P$ other than the two incident to $v_{i}$.

Proof.

A point $x$ on the edge $\overline{v_{i}v_{i+1}}$ at distance $\alpha$ from $v_{i}$ satisfies either $\alpha\leq r_{i}$, in which case $x\in D_{i}$, or $\lvert\overline{xv_{i+1}}\rvert=(r_{i}+r_{i+1})-\alpha<r_{i+1}$, in which case $x\in D_{i+1}$. For any $j\neq i$ we have $\lvert\overline{v_{i}v_{j}}\rvert\geq r_{i}+r_{j}>r_{i}$, so $v_{j}\notin D_{i}$. Finally, suppose $x\in D_{i}$ lies on an edge $e=\overline{v_{j}v_{j+1}}$ not incident to $v_{i}$. Since $e\subseteq D_{j}\cup D_{j+1}$, we have $x\in D_{\ell}$ for some $\ell\in\{j,j+1\}$ with $\ell\neq i$, and hence $\lvert\overline{v_{i}v_{\ell}}\rvert\leq\lvert\overline{v_{i}x}\rvert+\lvert\overline{xv_{\ell}}\rvert\leq r_{i}+r_{\ell}$. If $C_{i}$ and $C_{\ell}$ are non-consecutive this contradicts Definition 1(3). If they are consecutive, then equality holds throughout, so $x$ lies on the segment $\overline{v_{i}v_{\ell}}$—an edge of $P$ incident to $v_{i}$—at distance $r_{i}$ from $v_{i}$, an interior point of that edge since $0<r_{i}<r_{i}+r_{\ell}$. The edge $e$ thus meets the edge $\overline{v_{i}v_{\ell}}$ at an interior point of the latter, contradicting the simplicity of $P$. ∎

For a point $p$ of the plane, let

$$d_{i}(p)=\lvert\overline{pv_{i}}\rvert-r_{i}$$ (2–1)

denote the signed distance from $p$ to the circle $C_{i}$; thus $d_{i}(p)>0$ if and only if $p$ lies outside $D_{i}$.

Definition 2.

Given an $N$-gon of touching circles and a circle $C$ with center $p$ in the interior of $P$ and radius $\rho>0$, we say that $C$ can be added to the configuration if $d_{i}(p)\geq\rho$ for all $i$, and that it touches $C_{i}$ if $d_{i}(p)=\rho$. We call $C$ admissible if it can be added and touches at least three of the circles.

Note that an added circle is automatically contained in $P$. Indeed, by Lemma 1, every edge of $P$ is covered by the two disks centered at its endpoints, so a disk that avoids all the $D_{i}$ and whose center lies in $P$ cannot reach the boundary of $P$.

The reduction will only ever add admissible circles. When an admissible circle $C$ touching $C_{i_{1}},\dots,C_{i_{k}}$ (with $i_{1}<\cdots<i_{k}$, so $k\geq 3$, and the subscript $j$ of $i_{j}$ understood cyclically with respect to $k$) is added, the segments connecting $p$ to the centers $v_{i_{1}},\dots,v_{i_{k}}$ subdivide $P$ into $k$ smaller polygons of touching circles, as illustrated in Figure 1(a). The polygon between the tangencies at $C_{i_{j}}$ and $C_{i_{j+1}}$ has $g_{j}+2$ sides, where

$$g_{j}=i_{j+1}-i_{j}\pmod{N},\qquad\sum_{j=1}^{k}g_{j}=N.$$ (2–2)

We call $g_{1},\dots,g_{k}$ the gaps of the added circle. Every reduced polygon has at most $N-1$ sides if and only if every gap satisfies $g_{j}\leq N-3$. In particular, a circle nestled into a “corner” of the configuration, touching three consecutive circles $C_{i-1}$, $C_{i}$, $C_{i+1}$, has gaps $(1,1,N-2)$ and produces two triangles together with another $N$-gon, as in Figure 1(b); this is precisely the non-reducing placement observed by Lang, and the content of Theorem 1 is that a reducing placement always exists.

(a)

(b)

Figure 1: Two subdivision steps applied to the same octagon of touching circles ($N=8$). A circle (center marked) is added, and the segments from its center to the centers of the touched circles subdivide the octagon. (a) The added circle touches three of the circles with gaps $1$, $2$, $5$, producing a triangle, a quadrilateral, and a heptagon—each again a polygon of touching circles. (b) A circle nestled into a corner, touching three consecutive circles. The gaps are $(1,1,6)$, and the subdivision produces two triangles together with another octagon.

2.2 The medial axis

Let $\Omega\subset\mathbb{R}^{2}$ be a compact connected set which is the closure of its interior. A closed disk $\mathcal{D}\subseteq\Omega$ is maximal if it is not contained in any strictly larger disk contained in $\Omega$. The medial axis of $\Omega$ is

$$\mathfrak{M}(\Omega)=\{\,p\in\Omega:p\text{ is the center of a maximal disk}\,\},$$ (2–3)

where, by convention, the sharp corners of $\partial\Omega$—corner points whose interior angle is less than $\pi$, at which the maximal disk degenerates to a point—are included in $\mathfrak{M}(\Omega)$. For $p\in\mathfrak{M}(\Omega)$ with its corresponding maximal disk $\mathcal{D}_{p}$, the set $\mathcal{D}_{p}\cap\partial\Omega$ is called the contact set of $p$, and its connected components the contact components.

The medial axis was introduced by Blum [Blum 67] as a tool for shape description. A rigorous structure theory was developed by Choi, Choi, and Moon [Choi et al. 97] for the class of connected domains bounded by finitely many disjoint simple closed curves (allowing holes), each curve consisting of finitely many real-analytic pieces. All domains appearing in this paper belong to this class, and moreover all their boundary corners are sharp. We summarize the facts we need. Here a geometric graph is a subset of the plane which is a connected finite graph whose vertices are points and whose edges are real-analytic curves of finite length.

Theorem 2 (Choi–Choi–Moon [Choi et al. 97]).

Let $\Omega$ be a domain of the above class, other than a disk. Then the following hold.

1. $\mathfrak{M}(\Omega)$ is a geometric graph (their Theorem 8.2); if $\Omega$ is simply connected, it is a tree (by their Corollary 8.1).

2. The degree of a point $p\in\mathfrak{M}(\Omega)$ as a vertex of this graph equals the number of contact components of $p$ (their Section 8.2).

3. Every vertex of degree one is either a sharp corner of $\partial\Omega$, or the center of a maximal disk which osculates $\partial\Omega$ along its unique contact component (their Theorem 8.2).

4. For every point $q\in\partial\Omega$ other than a corner, there is a unique maximal disk whose contact set contains $q$; writing $\beta(q)$ for its center, the map $\beta$ is continuous away from the corners (their Theorem 7.2).

3 Proof of the main theorem

Fix an $N$-gon of touching circles as in Definition 1, and define its free region

$$\mathfrak{F}\;=\;\overline{\,P\setminus(D_{1}\cup\cdots\cup D_{N})\,},$$ (3–1)

the closure of the part of the polygon not covered by the disks. See Figure 2.

Figure 2: The free region $\mathfrak{F}$ (yellow) and its medial axis (blue) for the octagon of touching circles of Figure 1. The medial axis is a tree whose $N$ leaves are the tangency points $t_{i}$; its edges are arcs of Apollonius hyperbolas, and its internal vertices are exactly the centers of the admissible circles. Internal vertices are marked green if all their gaps are at most $N-3$, so that adding the corresponding circle leaves only polygons with at most $N-1$ sides, and red otherwise; Theorem 1 asserts that a green vertex always exists. The additions of Figure 1(a) and (b) are those at a green and at a red vertex of this tree, respectively.

Lemma 2.

With notation as above:

1. $C_{i}\cap P$ is a single arc $\mathcal{A}_{i}$, running from $t_{i-1}$ to $t_{i}$ and spanning the interior angle of $P$ at $v_{i}$;

2. the arcs $\mathcal{A}_{1},\dots,\mathcal{A}_{N}$ are pairwise disjoint except that consecutive arcs share a tangency point, and their union is a simple closed curve bounding $\mathfrak{F}$. Consequently $\mathfrak{F}$ is a simply connected domain of the class of Theorem 2, and the only corners of $\partial\mathfrak{F}$ are the $N$ points $t_{1},\dots,t_{N}$, at which two arcs meet in a cusp of interior angle zero—a sharp corner;

3. $D_{i}\cap P$ is the closed circular sector of $D_{i}$ spanning the interior angle of $P$ at $v_{i}$; in particular, for every $x\in D_{i}\cap P$, the segment $\overline{v_{i}x}$ lies in $P$.

Proof.

(1) By Lemma 1, the circle $C_{i}$ meets $\partial P$ only on the two edges incident to $v_{i}$; on each of these it meets exactly one point, namely the point at distance $r_{i}$ from $v_{i}$, which is a tangency point ($t_{i-1}$ or $t_{i}$) because the edge has length $r_{i}+r_{i+1}>r_{i}$ (respectively $r_{i-1}+r_{i}>r_{i}$). A circle crossing the boundary of $P$ exactly twice intersects $P$ in a single arc, namely the one emanating from the interior angle at $v_{i}$.

(2) Non-consecutive arcs are disjoint because the corresponding disks are; consecutive arcs share exactly the tangency point of their disks. The concatenation $\mathcal{A}_{1}\mathcal{A}_{2}\cdots\mathcal{A}_{N}$ is therefore a simple closed curve $\gamma$. To see $\partial\mathfrak{F}\subseteq\gamma$, let $x\in\partial\mathfrak{F}$. Since $P\setminus(D_{1}\cup\cdots\cup D_{N})\subseteq\mathfrak{F}$, the complement of $\mathfrak{F}$ is covered by the exterior of $P$ together with the disks; hence $x$, lying in the closure of this complement as well as in $\mathfrak{F}\subseteq P$, belongs to $\partial P\cup D_{1}\cup\cdots\cup D_{N}$, and therefore to some disk $D_{i}$, the boundary $\partial P$ being itself covered by the disks (Lemma 1). On the other hand, $x$ lies in no open disk, the open disks being disjoint from $P\setminus(D_{1}\cup\cdots\cup D_{N})$ and hence from its closure $\mathfrak{F}$. Thus $x\in C_{i}\cap P=\mathcal{A}_{i}\subseteq\gamma$. Conversely, each point of an arc $\mathcal{A}_{i}$ is a limit both of points of $\operatorname{int}D_{i}$ (removed from $\mathfrak{F}$) and of free points, so $\gamma\subseteq\partial\mathfrak{F}$. Finally, the complement of $\mathfrak{F}$ in the plane is precisely the union of the exterior of $P$ with the open disks $\operatorname{int}D_{i}$. Indeed, the exterior and the open disks are disjoint from $\mathfrak{F}$, as noted above; conversely, a point of the complement lying in $P$ belongs to some disk $D_{i}$ by the covering argument above, and not to the circle $C_{i}$ itself, whose points in $P$ make up the arc $\mathcal{A}_{i}\subseteq\mathfrak{F}$, so it lies in $\operatorname{int}D_{i}$. Each open disk is connected and meets the exterior of $P$, because the interior angle of $P$ at $v_{i}$ is less than $2\pi$, so that $D_{i}$ is not contained in $P$. The complement is therefore connected, and $\mathfrak{F}$ is the closed Jordan domain bounded by $\gamma$. In particular $\mathfrak{F}$ is simply connected, and it is not a disk. Its boundary consists of $N$ real-analytic pieces. At $t_{i}$ the two arcs $\mathcal{A}_{i}$ and $\mathcal{A}_{i+1}$ are tangent to the common tangent line of $C_{i}$ and $C_{i+1}$ and curve away from $\mathfrak{F}$ on either side, so the interior angle of $\mathfrak{F}$ at $t_{i}$ is zero.

(3) Inside $D_{i}$, each of the two edges incident to $v_{i}$ is a radius—it emanates from the center and leaves the disk at distance $r_{i}$, the edge being longer than $r_{i}$. The two radii cut $D_{i}$ into two closed circular sectors, and by Lemma 1 these radii are the only portions of $\partial P$ inside $D_{i}$; hence the interior of each sector, being connected and disjoint from $\partial P$, lies entirely inside or entirely outside $P$, and near $v_{i}$ the sector spanning the interior angle is the one inside. Thus $D_{i}\cap P$ is that closed sector, and it contains the radial segment $\overline{v_{i}x}$ for each of its points $x$. ∎

We now analyze the medial axis $\mathfrak{M}=\mathfrak{M}(\mathfrak{F})$ of the free region. In the following, the tree $\mathfrak{M}$ is understood combinatorially. Vertices of degree two, which merely subdivide edges, are suppressed, and by a vertex we mean a leaf or a point of degree at least three. This convention affects neither the leaves nor the components of $\mathfrak{M}\setminus\{p\}$ at any vertex $p$.

Lemma 3.

Let $\mathfrak{M}=\mathfrak{M}(\mathfrak{F})$. Then:

1. $\mathfrak{M}$ is a finite tree whose leaves are precisely the tangency points $t_{1},\dots,t_{N}$;

2. every non-leaf vertex $p$, of degree $k$, lies in the interior of $\mathfrak{F}$, and its maximal disk $\mathcal{D}_{p}$ has positive radius $\rho$ and touches exactly $k$ of the circles, say $C_{i_{1}},\dots,C_{i_{k}}$ with $i_{1}<\cdots<i_{k}$ (the subscript $j$ of $i_{j}$ understood cyclically with respect to $k$), each at a single point $q_{i_{j}}$ collinear with $p$ and $v_{i_{j}}$. In particular, the circle $\partial\mathcal{D}_{p}$ is admissible, touching exactly the circles $C_{i_{1}},\dots,C_{i_{k}}$;

3. with notation as in (2), the components $\mathfrak{M}_{1},\dots,\mathfrak{M}_{k}$ of $\mathfrak{M}\setminus\{p\}$ can be labeled so that the leaves lying in $\mathfrak{M}_{j}$ are precisely $t_{i_{j}},t_{i_{j}+1},\dots,t_{i_{j+1}-1}$; their number is the gap $g_{j}=i_{j+1}-i_{j}$.

Proof.

(1) By Lemma 2(2) and Theorem 2(1), $\mathfrak{M}$ is a finite tree. By Theorem 2(3), a leaf of $\mathfrak{M}$ is either a sharp corner of $\partial\mathfrak{F}$—that is, one of the $t_{i}$—or the center of a maximal disk osculating the boundary along a single contact component. The latter does not occur. At any point $q$ in the interior of an arc $\mathcal{A}_{i}$, the osculating circle of the boundary is $C_{i}$ itself, whose disk lies outside $\mathfrak{F}$; a maximal disk of $\mathfrak{F}$ tangent to $\mathcal{A}_{i}$ at $q$ lies on the opposite side of the common tangent line, so it cannot osculate the arc, and a contact along a subarc of $\mathcal{A}_{i}$ would force the maximal disk to coincide with $D_{i}$. Conversely, each $t_{i}$ is a leaf. In a sufficiently small neighborhood of $t_{i}$, the boundary of $\mathfrak{F}$ consists only of pieces of $\mathcal{A}_{i}$ and $\mathcal{A}_{i+1}$, so a maximal disk centered there must touch both, placing its center on the single analytic curve $\{\,x:d_{i}(x)=d_{i+1}(x)\,\}$—one branch of a hyperbola with foci $v_{i}$ and $v_{i+1}$, passing through $t_{i}$. Hence exactly one edge of $\mathfrak{M}$ ends at $t_{i}$.

(2) A non-leaf vertex $p$, of degree $k$, is not a corner of $\partial\mathfrak{F}$, since corners are leaves by part (1); and a maximal disk centered on $\partial\mathfrak{F}$ has radius zero, so $p\in\operatorname{int}\mathfrak{F}$ and $\rho=\min_{i}d_{i}(p)>0$. By Theorem 2(2), the contact set of $p$ has exactly $k$ components. We claim no contact point is a corner $t_{i}$. If $\lvert\overline{pt_{i}}\rvert=\rho$, then, since $t_{i}\in C_{i}$,

$$d_{i}(p)\;\leq\;\lvert\overline{pt_{i}}\rvert+\lvert\overline{t_{i}v_{i}}\rvert-r_{i}\;=\;\rho,$$

while $\mathcal{D}_{p}\subseteq\mathfrak{F}$ forces $d_{i}(p)\geq\rho$; so equality holds throughout, and $p$ lies on the ray from $v_{i}$ through $t_{i}$—that is, on the line of the edge $\overline{v_{i}v_{i+1}}$—at distance $r_{i}+\rho$ from $v_{i}$. But then, the edge having length $r_{i}+r_{i+1}$, we get $\lvert\overline{pv_{i+1}}\rvert=\lvert(r_{i}+\rho)-(r_{i}+r_{i+1})\rvert=\lvert\rho-r_{i+1}\rvert$, and so $d_{i+1}(p)=\lvert\rho-r_{i+1}\rvert-r_{i+1}<\rho$, contradicting $\mathcal{D}_{p}\subseteq\mathfrak{F}$. Thus every contact point lies in the interior of some arc $\mathcal{A}_{i}$. For such a contact point $q\in\mathcal{A}_{i}$ we have $\rho=\lvert\overline{pq}\rvert\geq d_{i}(p)\geq\rho$, so $q$ is the point of $C_{i}$ nearest to $p$, which is unique and collinear with $p$ and $v_{i}$. In particular each circle carries at most one contact point, the $k$ contact components are single points $q_{i_{1}},\dots,q_{i_{k}}$ on $k$ distinct circles, and $d_{i}(p)\geq\rho$ for every $i$ with equality exactly at the touched circles.

(3) Let $S_{j}\subset\partial\mathfrak{F}$ denote the stretch of the boundary running from $q_{i_{j}}$ to $q_{i_{j+1}}$ in the cyclic order, with the two endpoints excluded; walking from $q_{i_{j}}\in\mathcal{A}_{i_{j}}$ to $q_{i_{j+1}}\in\mathcal{A}_{i_{j+1}}$, one passes exactly the corners $t_{i_{j}},t_{i_{j}+1},\dots,t_{i_{j+1}-1}$—$g_{j}$ of them in total. Consider the map $\beta$ of Theorem 2(4), extended to the corners by letting $\beta(t_{m})=t_{m}$; this extension is continuous, since the inscribed radius at a boundary point tends to zero as the point approaches a cusp, being bounded by the width of the wedge between the two tangent disks. Thus $\beta(S_{j})$ is a connected subset of $\mathfrak{M}$. Moreover, $\beta$ never takes the value $p$ on $S_{j}$. If $\beta(q)=p$ for a boundary point $q$, then $q$ lies in the contact set of $p$, that is, $q$ is one of the points $q_{i_{1}},\dots,q_{i_{k}}$—and these are excluded from $S_{j}$. The connected set $\beta(S_{j})$ therefore avoids $p$ and lies in a single component of $\mathfrak{M}\setminus\{p\}$; call it $\mathfrak{M}_{(j)}$. Now every component $X$ of $\mathfrak{M}\setminus\{p\}$ contains at least one leaf of $\mathfrak{M}$ (walk within $X$ away from $p$ as far as possible), every leaf $t_{m}$ lies in exactly one stretch $S_{j}$ (contact points are not corners), and $t_{m}=\beta(t_{m})\in\mathfrak{M}_{(j)}$. Hence $j\mapsto\mathfrak{M}_{(j)}$ is a surjection from $k$ stretches onto the $k$ components of $\mathfrak{M}\setminus\{p\}$, and is therefore a bijection; and the leaves in $\mathfrak{M}_{(j)}$ are exactly those in $S_{j}$. ∎

The combinatorial heart of the proof, and its only non-geometric ingredient, is the following elementary fact about trees, which we call the tree lemma.

Lemma 4 (tree lemma).

Every finite tree $T$ with $L\geq 5$ leaves has a vertex $p$ of degree at least three such that every component of $T\setminus\{p\}$ contains at most $L-3$ leaves of $T$.

Proof.

Since $L\geq 3$, the tree $T$ is not a path, so it has a vertex of degree at least three.

First suppose some vertex $p$ has degree $k\geq 4$. The components of $T\setminus\{p\}$ each contain at least one leaf of $T$, and the $L$ leaves of $T$ are distributed among all $k$ of them; hence each component contains at most $L-(k-1)\leq L-3$ leaves of $T$.

Otherwise, every vertex has degree at most $3$; call those of degree exactly $3$ the branch vertices. Let $n_{1}=L$, $n_{2}$, and $n_{3}$ denote the numbers of vertices of degree $1$, $2$, and $3$, respectively. Counting degrees over the edges in two ways gives $2(n_{1}+n_{2}+n_{3}-1)=n_{1}+2n_{2}+3n_{3}$, so $n_{3}=n_{1}-2$, the count $n_{2}$ cancelling.

For a branch vertex, we say that a leaf is attached to it, if there is no other branch vertex in between them. If every branch vertex had at least two attached leaves, then $n_{1}\geq 2n_{3}=2n_{1}-4$, forcing $n_{1}\leq 4$ and contradicting $L\geq 5$. Hence some branch vertex $p$ has at most one attached leaf.

Each component of $T\setminus\{p\}$ either contains no branch vertex—being then a path from $p$ to the attached leaf, and there is at most one such component—or contains a branch vertex, and with it at least two leaves of $T$. Therefore, for each component, the other two components together contain at least $1+2=3$ leaves of $T$, so the component itself contains at most $L-3$. ∎

Lemma 5.

Let $p$ be a non-leaf vertex of $\mathfrak{M}$, of degree $k$, touching $C_{i_{1}},\dots,C_{i_{k}}$ as in Lemma 3(2), and add the circle $C=\partial\mathcal{D}_{p}$. Then the $k$ segments $\overline{pv_{i_{j}}}$ lie in $P$, meet one another only at $p$, and subdivide $P$ into $k$ simple polygons $P_{1},\dots,P_{k}$, where $P_{j}$ has vertices $p,v_{i_{j}},v_{i_{j}+1},\dots,v_{i_{j+1}}$. Together with the added circle and the circles at its vertices, each $P_{j}$ is a $(g_{j}+2)$-gon of touching circles.

Proof.

By Lemma 3(2), the points $p$, $q_{i_{j}}$, $v_{i_{j}}$ are collinear, so $\overline{pv_{i_{j}}}=\overline{pq_{i_{j}}}\cup\overline{q_{i_{j}}v_{i_{j}}}$ is a straight segment; the first part is a radius of $\mathcal{D}_{p}\subseteq\mathfrak{F}\subseteq P$, and the second lies in $P$ by Lemma 2(3). Being straight segments emanating from the common interior point $p$ toward distinct vertices of $P$, they meet only at $p$, and since their endpoints $v_{i_{1}},\dots,v_{i_{k}}$ occur on $\partial P$ in this cyclic order, the segments subdivide $P$ into $k$ simple polygons with the stated vertex lists. In $P_{j}$, consecutive circles among $C_{i_{j}},\dots,C_{i_{j+1}}$ are tangent as before; the new edges satisfy $\lvert\overline{pv_{i_{j}}}\rvert=\rho+r_{i_{j}}$ and $\lvert\overline{pv_{i_{j+1}}}\rvert=\rho+r_{i_{j+1}}$, so $C$ is tangent to the circles at both ends; and all remaining pairs in $P_{j}$ are disjoint—pairs of old circles by Definition 1(3), and $C$ from any old circle $C_{m}$ with $i_{j}<m<i_{j+1}$ because $d_{m}(p)>\rho$ strictly, as $C_{m}$ is not among the touched circles. Hence $P_{j}$ is a polygon of touching circles with $g_{j}+2$ vertices. ∎

Proof of Theorem 1.

Let $N>4$. By Lemma 3(1), the medial axis $\mathfrak{M}$ of the free region is a finite tree with $N\geq 5$ leaves. By the tree lemma (Lemma 4), $\mathfrak{M}$ has a non-leaf vertex $p$ such that every component of $\mathfrak{M}\setminus\{p\}$ contains at most $N-3$ leaves. Lemma 3(2) then provides an admissible circle $C=\partial\mathcal{D}_{p}$, and by Lemma 3(3) its gaps satisfy $g_{j}\leq N-3$ for all $j$. By Lemma 5, adding $C$ subdivides $P$ into polygons of touching circles with $g_{j}+2\leq N-1$ sides each. ∎

Since each polygon produced by the subdivision is again a polygon of touching circles, the reduction can be iterated. The following quantitative consequence is worth recording.

Corollary 2.1.

Every $N$-gon of touching circles can be subdivided into triangles and quadrilaterals of touching circles by adding at most $N-4$ circles.

Proof.

We argue by induction on $N$ that at most $\max(0,N-4)$ added circles suffice. For $N\leq 4$ there is nothing to prove. For $N\geq 5$, Theorem 1 provides a circle whose addition subdivides the polygon into $k\geq 3$ reduced polygons with $g_{j}+2$ sides, where $\sum_{j}g_{j}=N$ and $g_{j}\leq N-3$; by the induction hypothesis, each of them can be subdivided further using at most $\max(0,g_{j}-2)$ added circles. The total number of added circles is therefore at most

$$1+\sum_{j}\max(0,g_{j}-2)\;=\;1+(N-h)-2(k-h)\;=\;1+N-2k+h,$$

where $h$ is the number of gaps equal to $1$—such gaps contribute nothing, while the remaining $k-h$ gaps sum to $N-h$ and each is shortened by $2$. We claim $2k-h\geq 5$, so that the total is at most $N-4$. If $h=k$, then every gap is $1$ and $2k-h=k=N\geq 5$. If $k=3$, then $h\leq 1$—two gaps equal to $1$ would force the third to be $N-2>N-3$—and $2k-h\geq 5$. And if $k\geq 4$ with $h\leq k-1$, then $2k-h\geq k+1\geq 5$. ∎

4 The explicit construction

The proof of Theorem 1 is constructive, and we record the resulting procedure explicitly as Algorithm 1. The edges of $\mathfrak{M}$ are, by the proof of Lemma 3, arcs of the bisector curves $\{d_{i}=d_{j}\}$, each of which is a branch of a hyperbola with foci $v_{i}$ and $v_{j}$, the Apollonius hyperbola of the two circles. The medial axis of $\mathfrak{F}$ is thus the portion, inside the free region, of the Apollonius diagram (the additively weighted Voronoi diagram [Lee and Drysdale 81]) of the $N$ circles.

Algorithm 1 (reduction step).

Input: an $N$-gon of touching circles with $N>4$. Output: an added circle leaving only polygons with at most $N-1$ sides.

1. Maintain a cyclic list of bisector arcs, initialized with the $N$ arcs of consecutive pairs $(C_{i},C_{i+1})$, each emanating from its tangency point $t_{i}$.

2. While more than three arcs remain, search the adjacent pairs of arcs for a valid intersection point $p$. For adjacent arcs of pairs $(C_{a},C_{b})$ and $(C_{b},C_{c})$, the two bisector curves cross in at most two points, and such a point $p$ is valid if it lies inside $P$ with $d_{m}(p)\geq d_{a}(p)$ for every circle $C_{m}$ not among the pairs; not every adjacent pair admits a valid point, but some pair always does. Record a valid $p$ as an internal vertex of $\mathfrak{M}$, touching $C_{a},C_{b},C_{c}$, and replace the two arcs by the bisector arc of $(C_{a},C_{c})$ emanating from $p$. When three arcs remain, record their common valid intersection as the last vertex.

3. For each recorded vertex, read off its gaps from the touched indices by equation (2–2); return the maximal disk of any vertex whose gaps are all at most $N-3$, which exists by Theorem 1.

Each merge in step (2) contracts a pair of adjacent leaves of the current tree into their common neighbor, so the loop enumerates the internal vertices of $\mathfrak{M}$ (a vertex of degree $k$ arising as $k-2$ coincident merges) and terminates after at most $N-3$ merges. We justify the two assertions made in step (2). An adjacent pair need not admit a valid point because the two bisector curves may well cross at a point that is not a vertex of $\mathfrak{M}$ at all, which happens when one of the two arcs runs into the arc of a third circle first. The validity test is what detects this. Validity is exactly the condition that the disk at the intersection avoids all other circles, so, as in Lemma 3(2), the valid points are precisely the internal vertices of $\mathfrak{M}$; at a premature intersection $p$, the intruding third circle is nearer to $p$ than $d_{a}(p)$, and $p$ fails the test. And some pair always admits a valid point. In the current tree, the second vertex of a longest path has at most one branch that is not a single leaf, so at least two of its leaf branches are cyclically adjacent, and these two arcs intersect validly at that vertex. A straightforward implementation—ours, which produced all the figures in this paper—spends $O(N)$ candidate checks of cost $O(N)$ per merge, hence $O(N^{3})$ time in the worst case. Asymptotically better bounds follow from computational geometry. The Apollonius diagram of $N$ circles can be computed in $O(N\log N)$ time by Fortune’s sweepline algorithm [Fortune 87], and step (3) is linear, so a single reduction step costs $O(N\log N)$, and the full subdivision of Corollary 2.1 costs $O(N^{2}\log N)$.

Since the motivation for reducing to triangles and quadrilaterals is that those molecules admit direct geometric constructions, it is worth recording that the reduction itself demands nothing beyond straightedge and compass. An internal vertex $p$ of $\mathfrak{M}$ and the radius $\rho$ of its maximal disk satisfy $\lvert\overline{pv_{i}}\rvert=\rho+r_{i}$ for each touched circle $C_{i}$. For any three of the touched circles, this is the classical tangency problem of Apollonius. Although the equations are quadratic, squaring and subtracting the equation of one touched circle $C_{a}$ from those of two others cancels all quadratic terms. Writing $\mathchoice{\overarrow@\to{x}}{\overarrow@\to{x}}{\overarrow@\to{x}}{\overarrow@\to{x}}$ for the position vector of a point $x$ in a fixed Cartesian frame, what remains is the pair of linear equations

$$2\bigl(\mathchoice{\overarrow@\to{v_{i}}}{\overarrow@\to{v_{i}}}{\overarrow@\to{v_{i}}}{\overarrow@\to{v_{i}}}-\mathchoice{\overarrow@\to{v_{a}}}{\overarrow@\to{v_{a}}}{\overarrow@\to{v_{a}}}{\overarrow@\to{v_{a}}}\bigr)\cdot\mathchoice{\overarrow@\to{p}}{\overarrow@\to{p}}{\overarrow@\to{p}}{\overarrow@\to{p}}+2(r_{i}-r_{a})\,\rho\;=\;\bigl(\lvert\mathchoice{\overarrow@\to{v_{i}}}{\overarrow@\to{v_{i}}}{\overarrow@\to{v_{i}}}{\overarrow@\to{v_{i}}}\rvert^{2}-r_{i}^{2}\bigr)-\bigl(\lvert\mathchoice{\overarrow@\to{v_{a}}}{\overarrow@\to{v_{a}}}{\overarrow@\to{v_{a}}}{\overarrow@\to{v_{a}}}\rvert^{2}-r_{a}^{2}\bigr),$$

which determine $p$ as an affine function of $\rho$; substituting back into $\lvert\overline{pv_{a}}\rvert^{2}=(\rho+r_{a})^{2}$ then leaves a single quadratic equation in $\rho$. The center and radius of each added circle therefore lie in a quadratic extension of the field generated, over the rationals, by the center coordinates and radii of the current configuration, and since the validity test in step (2) and the gap counts in step (3) only compare such quantities, the entire subdivision of Corollary 2.1 can be carried out with straightedge and compass. This linearization is classical. It is precisely how Courant and Robbins [Courant and Robbins 96, pp. 125–127] show that the tangency problem of Apollonius is solvable by straightedge and compass, and an elegant explicit construction, via inversion, is given in the same reference, pp. 161–162. Everything above applies verbatim to the inflated configurations of Sections 6 and 7, in which $r_{i}$ is replaced by $r_{i}+w$ or $r_{i}+W_{i}$. (Our implementation computes the vertices from this quadratic in closed form.)

5 Optimality of the bound

The bound of Corollary 2.1 cannot be improved. In this section, for arbitrarily large $N$, we construct $N$-gons of touching circles that cannot be subdivided into triangles and quadrilaterals by fewer than $N-4$ added circles (Corollary 2.2). The witnesses form a family of one simple shape—two half-staggered rows of equal circles closed by two small caps—and the plan is equally simple. Subdividing a member of the family leaves, besides triangles and quadrilaterals, only smaller members of the same family, so the conclusion follows by induction. We begin with a bottleneck estimate at the interlocking ends of two rows.

Lemma 6 (throat lemma).

Let $D_{i}$ and $D_{j}$ be two disks of radius $4$ whose centers $v_{i}$ and $v_{j}$ are at distance $4\sqrt{5}$, and call the part of the segment $\overline{v_{i}v_{j}}$ outside the two disks, of length $4\sqrt{5}-8$, their throat. Then every disk avoiding the interiors of $D_{i}$ and $D_{j}$ and containing a point of the throat has radius at most $\tfrac{1}{2}$.

Proof.

Let the disk have center $p$ and radius $\rho$, and let $q$ be a point of the throat inside it. Write $\delta_{i}=\lvert\overline{qv_{i}}\rvert$ and $\delta_{j}=\lvert\overline{qv_{j}}\rvert$, so that $\delta_{i},\delta_{j}\geq 4$ and $\delta_{i}+\delta_{j}=4\sqrt{5}$. Work in Cartesian coordinates with origin $v_{i}$ and first axis in the direction of $v_{j}$, so that $q=(\delta_{i},0)$, and let $\alpha$ denote the first coordinate of $p$. The second coordinates of $\mathchoice{\overarrow@\to{p}}{\overarrow@\to{p}}{\overarrow@\to{p}}{\overarrow@\to{p}}-\mathchoice{\overarrow@\to{v_{i}}}{\overarrow@\to{v_{i}}}{\overarrow@\to{v_{i}}}{\overarrow@\to{v_{i}}}$ and $\mathchoice{\overarrow@\to{p}}{\overarrow@\to{p}}{\overarrow@\to{p}}{\overarrow@\to{p}}-\mathchoice{\overarrow@\to{q}}{\overarrow@\to{q}}{\overarrow@\to{q}}{\overarrow@\to{q}}$ coincide, so $\lvert\overline{pv_{i}}\rvert^{2}-\alpha^{2}=\lvert\overline{pq}\rvert^{2}-(\alpha-\delta_{i})^{2}$, that is, $\lvert\overline{pv_{i}}\rvert^{2}=\lvert\overline{pq}\rvert^{2}+2\delta_{i}\alpha-\delta_{i}^{2}$. Combining this with the constraints $(4+\rho)^{2}\leq\lvert\overline{pv_{i}}\rvert^{2}$ and $\lvert\overline{pq}\rvert\leq\rho$ gives $(4+\rho)^{2}\leq\rho^{2}+2\delta_{i}\alpha-\delta_{i}^{2}$, that is,

$$\alpha\geq\frac{16+8\rho}{2\delta_{i}}+\frac{\delta_{i}}{2},\quad\text{and symmetrically}\quad 4\sqrt{5}-\alpha\geq\frac{16+8\rho}{2\delta_{j}}+\frac{\delta_{j}}{2}.$$

Adding and using $1/\delta_{i}+1/\delta_{j}\geq 4/(\delta_{i}+\delta_{j})$,

$$4\sqrt{5}\;\geq\;(8+4\rho)\left(\frac{1}{\delta_{i}}+\frac{1}{\delta_{j}}\right)+\frac{\delta_{i}+\delta_{j}}{2}\;\geq\;\frac{8+4\rho}{\sqrt{5}}+2\sqrt{5},$$

so $\rho\leq\tfrac{1}{2}$. ∎

Call a polygon of touching circles a two-row configuration if its circles are as follows. Two rows of radius-$4$ circles, tangent consecutively within each row, have their centers on two parallel lines at distance $8$, and the two rows are offset against each other by $4$—half the center spacing. At each end, the rows terminate in a pair of extreme circles, one per row, whose centers we require to be at distance $\sqrt{4^{2}+8^{2}}=4\sqrt{5}$; the rows thus overhang each other by exactly $4$ at each end, and their lengths differ by at most one circle. Finally, at each end sits a cap, a circle tangent to the two extreme circles of that end, whose disk avoids their throat. The component of $\operatorname{int}P$ minus the two extreme disks and the throat that contains the cap is called the end zone of that end, and we require that the closure of each end zone meet no circle other than its cap and its two extremes.

The end zone is always contained in the triangle spanned by the two extreme centers and the center of the cap. Indeed, the boundary of $P$ near the end consists of the two edges joining the cap center to the two extreme centers, which are covered by their tangent disks (Lemma 1), while the throat lies on the segment joining the extreme centers.

For $k\geq 5$, we write $T_{k}$ for the special case of a two-row configuration with $k$ circles in total in which both caps have radius exactly $1$. The general family, whose caps are only required to satisfy the conditions above, is what the induction below runs on; $T_{k}$ is its canonical member, and is determined up to isometry. Indeed, the $k-2$ row circles split into two rows whose lengths differ by at most one, and a cap of radius $1$, being tangent to the two extreme disks of its end, has its center at distance exactly $\sqrt{3^{2}+4^{2}}=5=4+1$ from the two extreme centers—on the far side of their segment from the rows, the near side being excluded by the end-zone requirement. Placing the row centers at the points $(8i,0)$ and $(8i+4,8)$, all the remaining requirements hold—two circles of opposite rows are at distance at least $4\sqrt{5}>8$, and each end-zone triangle is at distance greater than $7$ from every center outside its end, so the end zones indeed meet no other circles. Thus $T_{k}$ is a $k$-gon of touching circles; Figure 3 shows $T_{9}$.

Figure 3: The configuration $T_{9}$, two half-staggered rows of radius-$4$ circles closed by two radius-$1$ caps, shown with the medial axis of its free region and with the cap, end zone, and throat of its left end labeled. The five green vertices are the integer points $(8i+4,3)$ and $(8i+8,5)$, whose maximal disks have radius exactly $1$. All seven internal vertices have degree $3$ and touch a consecutive pair, and the subdivision at any vertex leaves—besides triangles and quadrilaterals—only two-row configurations again (Proposition 1).

Proposition 1.

In a two-row configuration, every admissible circle touches exactly three circles, of which two are consecutive; and every reduced polygon of the resulting subdivision with at least five sides is again a two-row configuration.

Proof.

Consider first a circle that can be added, whose disk meets a closed end zone or a throat. If it meets a throat, then by Lemma 6 it has radius at most $\tfrac{1}{2}$, and its center lies within $1$ of the segment joining the two extreme centers; that segment is at distance greater than $7$ from the center of every circle other than the cap and the two extreme circles, so the disk, at distance greater than $6>4+\tfrac{1}{2}$ from all such centers, touches none of them. If it avoids the throats, then, being connected and disjoint from the interiors of the extreme disks, it lies inside the end zone, whose closure meets no other circle. In either case the circle can touch only the cap and the two extreme circles of that end. If it is admissible, it therefore touches exactly these three circles, so $k=3$, and two of the touched circles are consecutive—indeed the cap is consecutive to both extremes.

Otherwise the disk avoids the closed end zones and the throats, and hence touches only circles of the rows. Place the configuration so that the centers of one row are at points $(8i,0)$ and those of the other at points $(8j+4,8)$, for integers $i$ and $j$. We claim that, if the circle is admissible, it touches exactly two consecutive circles of one row and one circle of the other—so $k=3$ with a consecutive pair, as required. This follows from two features of the rows. First, a free disk between them is too small to reach two non-consecutive circles of a row; second, the half-stagger puts the candidate centers for the two rows on disjoint vertical lines, ruling out two touches per row. Quantitatively, consider a free disk centered at $(x,y)$ with $x$ in the common span of the rows—the interval of abscissas covered by both—so that each row, its centers spaced $8$ apart, has a center within horizontal distance $4$ of $x$. The disk then has radius at most

$$\min\left(\sqrt{16+y^{2}},\,\sqrt{16+(8-y)^{2}}\right)-4\;\leq\;\sqrt{32}-4\;<\;4,$$

the two entries of the minimum bounding its distances to the nearest center of the bottom and of the top row, and the minimum being largest at $y=4$; while a disk touching two non-consecutive circles of the same row, whose centers are at distance at least $16$, has radius at least $4$. Such a circle therefore touches at most two circles per row, and only consecutive ones. Moreover a disk touching two consecutive bottom circles is centered on a line $x=8i+4$, and one touching two consecutive top circles on a line $x=8j+8$; these lines are disjoint, so no circle touches two circles of each row. An admissible circle, touching at least three circles in total, therefore touches exactly two consecutive circles of one row and one circle of the other. Concretely, in $T_{k}$, placed as in Figure 3, the resulting vertices are the integer points $(8i+4,3)$ and $(8i+8,5)$, whose maximal disks have radius exactly $1$. Each is at distance $5$ from its three touched circles, and at distance at least $\sqrt{64+25}=\sqrt{89}>5+1$ from the centers of all other circles of radius $4$.

It remains to examine the reduced polygons, the added circle being of one of the two kinds just identified. A circle added over the rows splits the configuration, by Lemma 5, into a triangle and one or two shorter configurations of the very same two-row form, in which the added radius-$1$ disk becomes a cap. For instance, a disk added at $(4,3)$, as a cap for the extreme circles at $(8,0)$ and $(4,8)$, is again tangent to both at distance $5$; its center lies at distance $\sqrt{5}$ from the segment joining the two extreme centers, on the end-zone side, so the disk of radius $1$ avoids their throat—the same integer data as the original caps, reflected. A circle added at an end cuts off two triangles and leaves an $N$-gon with the same rows and extremes, in which the added disk—contained in the same end zone and tangent to the two extreme circles—becomes the new, smaller cap. In both cases each new cap is tangent to its two extreme circles and its disk lies in the corresponding end zone, which meets no other circle, so every reduced polygon with at least five sides satisfies the definition of a two-row configuration. ∎

Corollary 2.2.

For arbitrarily large $N$ there exist $N$-gons of touching circles that cannot be subdivided into triangles and quadrilaterals by fewer than $N-4$ added circles.

Proof.

Since $T_{N}$ is a two-row configuration with $N$ sides for every $N\geq 5$, it suffices to show that subdividing a two-row configuration with $N$ sides into triangles and quadrilaterals requires at least $N-4$ added circles. We argue by induction on the total number of circles added. Since $N\geq 5$, at least one circle is added. By Proposition 1, the first one touches exactly three circles with a consecutive pair, so its gaps are $1,g_{2},g_{3}$ with $g_{2}+g_{3}=N-1$, and it subdivides the polygon into a triangle together with reduced polygons of $g_{2}+2$ and $g_{3}+2$ sides. Every later circle is added inside one of these reduced polygons, and a reduced polygon with $g_{j}+2\geq 5$ sides is again a two-row configuration (Proposition 1), whose complete subdivision uses at least $g_{j}-2$ added circles by the induction hypothesis. The total number of added circles is therefore at least $1+\max(0,g_{2}-2)+\max(0,g_{3}-2)$. One case to watch for is $g_{j}=1$, arising when the first circle is added at an end. The large reduced polygon then has $N$ sides again—the same rows with a smaller cap—so the addition was a wasted move, and this is why the induction runs on the number of added circles rather than on $N$. The arithmetic confirms the picture. When $g_{2},g_{3}\geq 2$ the total is at least $1+(g_{2}-2)+(g_{3}-2)=N-4$; and when some $g_{j}=1$, the other gap is $N-2$, and the total is at least $1+(N-2)-2=N-3$. In either case at least $N-4$ circles are added. ∎

6 Polygons with rivers

In the circle/river method, a river is a curved strip of constant width representing a segment shared by several flaps; within an axial polygon, a river enters through one gap between consecutive circles and leaves through another, separating the circles of the polygon into two groups. We now show that Theorem 1 persists in the presence of a river.

Definition 3.

An $N$-gon of touching circles with a river of width $w>0$ consists of a simple polygon $P$ with vertices $v_{1},\dots,v_{N}$, circles $C_{i}$ centered at $v_{i}$ with radii $r_{i}>0$, and two distinguished non-adjacent edge indices $a\neq b$, partitioning the circles into the two banks $A=\{C_{a+1},\dots,C_{b}\}$ and $B=\{C_{b+1},\dots,C_{a}\}$, such that

1. $\lvert\overline{v_{i}v_{i+1}}\rvert=r_{i}+r_{i+1}$ for $i\neq a,b$, while $\lvert\overline{v_{i}v_{i+1}}\rvert=r_{i}+r_{i+1}+w$ for $i\in\{a,b\}$; and

2. $\lvert\overline{v_{i}v_{j}}\rvert>r_{i}+r_{j}$ for non-consecutive $C_{i},C_{j}$ on the same bank, and $\lvert\overline{v_{i}v_{j}}\rvert>r_{i}+r_{j}+w$ for non-consecutive $C_{i},C_{j}$ on opposite banks.

In the underlying design, the river enters $P$ through the gap on the edge $\overline{v_{a}v_{a+1}}$, separates the flaps of $A$ from those of $B$, and leaves through the gap on $\overline{v_{b}v_{b+1}}$.

Figure 4(a) shows an octagon of touching circles with a river. We assume throughout this section that the circle is to be added on the bank $A$; this loses no generality, as exchanging the indices $a$ and $b$ exchanges the two banks. A circle $C$ with center $p\in\operatorname{int}P$ and radius $\rho$ added on the bank $A$ must not overlap the circles of $A$, and must in addition leave room for the river to pass between itself and every circle of $B$; that is,

$$d_{i}(p)\geq\rho\quad\text{for }C_{i}\in A,\qquad d_{i}(p)\geq\rho+w\quad\text{for }C_{i}\in B.$$ (6–1)

When equality holds we say that $C$ touches $C_{i}$ (for $C_{i}\in A$), or touches it across the river (for $C_{i}\in B$); in the latter case the segment $\overline{pv_{i}}$ has length $\rho+w+r_{i}$, matching the length of an axial-polygon edge crossed by the river. Subdividing along the segments from $p$ to the touched centers then decomposes $P$ exactly as in Lemma 5, with the river now threading through those sub-polygons whose boundary separates the two banks; the count of (2–2) is unchanged.

(a)

(b)

(c)

Figure 4: (a) An octagon of touching circles with a river of width $w$ (shaded orange), drawn as the designer conceives it—a strip of width $w$ entering and leaving the polygon through the two gaps. (b), (c) The medial axes (blue) of the free regions of the two expanded configurations of the same example. In (b) the circles of one bank, and in (c) those of the other, are enlarged by $w$ (enlarged circles are drawn with double outlines), and the collar between the original and the enlarged circles—the region along which the river is rerouted in the proof of Theorem 3—is shaded in the same orange. Consecutive enlarged circles overlap, and their boundary arcs meet transversally instead of at cusps; the medial axis is nevertheless a tree with $N=8$ leaves in both cases. Internal vertices are colored green or red as in Figure 2. The two choices of bank yield two different reductions of the same configuration.

The device of the proof is to absorb the river into the circles of the bank $B$, and to perform the absorption continuously. For $t\in[0,w]$ define

$$\tilde{r}_{i}(t)=r_{i}\quad\text{for }C_{i}\in A,\qquad\tilde{r}_{i}(t)=r_{i}+t\quad\text{for }C_{i}\in B,$$ (6–2)

write $\tilde{C}_{i}(t)$, $\tilde{D}_{i}(t)$ for the corresponding circles and disks, and let

$$\mathfrak{F}(t)\;=\;\overline{P\setminus(\tilde{D}_{1}(t)\cup\cdots\cup\tilde{D}_{N}(t))}$$

be the free region at time $t$, which shrinks as $t$ grows. At $t=w$ we obtain the expanded configuration. By (6–1), a circle can be added on the bank $A$ exactly when it can be added to the expanded configuration in the sense of Definition 2. The expanded configuration is no longer a polygon of touching circles in the strict sense. Consecutive circles within the bank $B$ overlap, their boundaries crossing transversally (Figure 4), the two gap pairs become tangent, and in degenerate configurations an expanded disk may even swallow the free arcs of other circles of $B$ entirely (Figure 5). Rather than excluding such degenerations, we track them along the shrinking process. For $t<w$, the boundary of $\mathfrak{F}(t)$ contains two segments of length $w-t$ on the gap edges, which we call the mouths. They are the openings through which the river enters and leaves the polygon, and at $t=w$ they close into two tangency cusps.

(a)

(b)

Figure 5: A hexagon of touching circles with a river, expanded on either bank (enlarged circles drawn with double outlines, the collar shaded orange as in Figure 4). In both (a) and (b) the expansion is degenerate: the middle circle of the expanded bank is swallowed by its two enlarged neighbors, its free arc disappearing entirely, so that the boundary of the free region runs from one neighbor directly to the other.

Two consequences of Definition 3 confine all degeneration strictly to the interior of the expanded bank.

Lemma 7 (bank integrity).

For all $t\in[0,w]$ and every $C_{j}\in B$:

1. $\tilde{D}_{j}(t)$ meets no disk of the bank $A$, except that the two gap pairs become tangent at $t=w$; in particular it contains no center of a circle of $A$ and meets no edge of $P$ joining two circles of $A$;

2. the interior of $\tilde{D}_{j}(t)$ contains no point of either mouth.

Proof.

(1) For $C_{m}\in A$ non-consecutive to $C_{j}$, Definition 3 gives $\lvert\overline{v_{j}v_{m}}\rvert>r_{j}+r_{m}+w\geq\tilde{r}_{j}(t)+r_{m}$; for the gap pairs, $\lvert\overline{v_{j}v_{m}}\rvert=r_{j}+r_{m}+w\geq\tilde{r}_{j}(t)+r_{m}$, with equality only at $t=w$. An edge joining two circles of $A$ is covered by their disks, so meeting it would mean meeting a disk of $A$.

(2) If $C_{j}$ is the bank-$B$ circle of the mouth’s own gap edge, the mouth consists by definition of points at distance at least $\tilde{r}_{j}(t)$ from $v_{j}$. Otherwise, let $C_{m}\in A$ be the bank-$A$ circle of that gap edge; every point $q$ on the mouth satisfies $\lvert\overline{qv_{m}}\rvert\leq r_{m}+(w-t)$, so $q\in\tilde{D}_{j}(t)$ would give

$$\lvert\overline{v_{j}v_{m}}\rvert\;\leq\;(r_{j}+t)+(r_{m}+(w-t))\;=\;r_{j}+r_{m}+w,$$

contradicting Definition 3 for the non-consecutive cross-bank pair $C_{j}$, $C_{m}$. ∎

The next lemma is the structural heart of this section—no matter how badly the expanded bank degenerates, the boundary of the free region can never scramble the circles.

Lemma 8 (shrinking lemma).

For every $t\in[0,w]$, each connected component of $\mathfrak{F}(t)$ is bounded by circular arcs of distinct circles—at most one arc per circle—occurring along the boundary in their cyclic index order, interleaved in the correct position with at most two mouth segments.

Proof.

At $t=0$ the circles are pairwise tangent or disjoint with the strict clearances of Definition 3, and the proofs of Lemmas 1 and 2 apply verbatim except on the two gap edges, where the uncovered mouths appear. Thus $\mathfrak{F}(0)$ is a single component bounded by the $N$ arcs in cyclic order and the two mouths. It remains to show that this structure can only degenerate, never reorganize, as $t$ grows.

First, boundary material only disappears, never appears. Fix $C_{j}\in B$ and a unit vector $u$, and follow the point $p(t)$ with $\mathchoice{\overarrow@\to{p}}{\overarrow@\to{p}}{\overarrow@\to{p}}{\overarrow@\to{p}}(t)=\mathchoice{\overarrow@\to{v_{j}}}{\overarrow@\to{v_{j}}}{\overarrow@\to{v_{j}}}{\overarrow@\to{v_{j}}}+\tilde{r}_{j}(t)\,u$ of $\tilde{C}_{j}(t)$. Call the direction $u$ dead at time $t$ if $p(t)$ lies in the interior of another expanded disk or outside $P$. Death is permanent. If $p(t_{0})\in\tilde{D}_{m}(t_{0})$ for some $C_{m}\in B$, then for $t\geq t_{0}$,

$$\lvert\overline{p(t)\,v_{m}}\rvert\;\leq\;\lvert\overline{p(t_{0})\,v_{m}}\rvert+(t-t_{0})\;\leq\;\tilde{r}_{m}(t_{0})+(t-t_{0})\;=\;\tilde{r}_{m}(t),$$

since $p$ moves with unit speed while $\tilde{D}_{m}$ grows with unit speed; disks of $A$ never meet $\tilde{C}_{j}(t)$ at all, by Lemma 7(1); and if $p(t_{0})$ exits $P$, then at the first later time at which $p$ returns to $\partial P$, the return point is neither on a vertex or edge of the bank $A$ (Lemma 7(1)) nor on a mouth (Lemma 7(2)), so it lies on a part of an edge covered by the expanded disk of a circle of $B$—and such coverage is permanent by the first computation. The points of the circles of $A$, finally, are never covered by anything. Hence every boundary arc—viewed as the set of directions $u$ it spans, its radius never decreasing—can only shrink, split, or vanish, and no circle ever contributes new boundary material.

Second, the combinatorial structure changes only at finitely many critical times, namely when an arc or mouth degenerates to a point, or when two expanded circles become tangent at a point of the closure of the free region (tangencies occurring inside covered territory or outside $P$ are invisible); by Lemma 7, such a tangency can only involve two circles of $B$, or a gap pair at the final time $t=w$, where a mouth closes into a cusp. When an arc or mouth degenerates, one entry is deleted from the boundary sequence of its component, which preserves the asserted structure. When two circles become tangent at a free point, the free region is pinched there, and the two local sides of the pinch end up in different components. Suppose not. Then some path inside the free region joins the two sides, and, closed up through the contact point, it yields a Jordan curve $J$ contained in the interior of $P$. Near the contact point, the two tangent disks lie on opposite local sides of $J$, so $J$ encloses one of the two disks—and with it the disk’s center, which is a vertex of $P$. On the other hand, $\partial P$ is connected, avoids $J$, and reaches points arbitrarily far away, so all of $\partial P$ lies outside $J$; in particular every vertex of $P$ does, a contradiction. So the pinch splits the component in two, and each new component inherits a contiguous run of the old boundary sequence, together with the new corner. In all cases the invariant survives, and the lemma follows by induction over the critical times. ∎

Lemma 9.

At $t=w$, some component $\mathfrak{F}_{\ast}$ of $\mathfrak{F}(w)$ carries on its boundary the arcs of all circles of $A$, the two mouth cusps, and arcs of the two circles of $B$ adjacent to the gap edges.

Proof.

By Lemma 7, no expanded disk meets any point of an arc $\mathcal{A}_{m}$ of a circle $C_{m}\in A$, so the free side of the whole $A$-chain survives at $t=w$. The free points at sufficiently small positive distance from the arcs of the chain form a connected set—it passes through the interior wedges at the tangency cusps of the chain—and hence lie in a single component $\mathfrak{F}_{\ast}$. The boundary of $\mathfrak{F}_{\ast}$ then contains every $\mathcal{A}_{m}$, the two mouth cusps at the two ends of the chain, and, beyond each mouth cusp, an initial piece of the arc of the adjacent expanded circle bounding the same wedge. ∎

Theorem 3.

For any $N$-gon of touching circles with a river, with $N>4$, it is possible to add a circle on either bank, touching at least three of the circles—directly or across the river—so that the largest reduced polygon has at most $N-1$ sides.

Proof.

Let $\mathfrak{F}_{\ast}$ be the component of Lemma 9, and let $\mathfrak{M}=\mathfrak{M}(\mathfrak{F}_{\ast})$. By Lemma 8, $\partial\mathfrak{F}_{\ast}$ consists of arcs of distinct circles in cyclic index order, meeting at corners which are tangency cusps or transversal crossings; at a crossing the free region occupies the sector outside both disks, whose angle is less than $\pi$, so all corners are sharp and $\mathfrak{F}_{\ast}$ is a simply connected domain of the class of Theorem 2. The analysis of Lemma 3 applies to $\mathfrak{M}$ with one modification. In the proof of Lemma 3(2) we showed that no contact point of a maximal disk is a corner of the boundary; there every corner was a tangency cusp, whereas here a corner may also be a transversal crossing, which requires an argument of its own. If a maximal disk centered at $p$ made contact at a transversal crossing $x$ of two expanded circles, then $x$ would be the point of each of the two circles nearest to $p$, forcing $p$ to lie on the ray through $x$ from each of the two centers; these rays are distinct, so $p=x$ and $\rho=0$, a contradiction. Thus $\mathfrak{M}$ is a finite tree whose leaves are the corners of $\partial\mathfrak{F}_{\ast}$; every non-leaf vertex, of degree $k$, is the center of a disk touching exactly $k$ of the expanded circles, each of which contributes an arc to $\partial\mathfrak{F}_{\ast}$, since the contact points of a maximal disk of $\mathfrak{F}_{\ast}$ lie on $\partial\mathfrak{F}_{\ast}$; and the leaves of $\mathfrak{M}$ are distributed among the branches at such a vertex according to the boundary stretches, as in Lemma 3(3). By (6–1), the circle bounding such a maximal disk can be added on the bank $A$, touching the corresponding circles directly (bank $A$) or across the river (bank $B$).

Call a circle hidden if it contributes no arc to $\partial\mathfrak{F}_{\ast}$. By Lemma 9, the circles of $A$ and the two circles of $B$ next to the gap edges are never hidden, so at least $|A|+2\geq 4$ circles contribute arcs, the gap edges being non-adjacent.

Case 1: at least five circles contribute arcs. The leaves of $\mathfrak{M}$ are the corners of $\partial\mathfrak{F}_{\ast}$, one between each pair of consecutive contributing arcs, so their number $L\geq 5$ equals the number of contributing circles. Consider a non-leaf vertex and one of its branches, running between consecutively touched circles $C_{i_{j}}$ and $C_{i_{j+1}}$. The branch contains one leaf for each contributing circle strictly between the two, plus one, while the gap $g_{j}$ counts one for every circle strictly between the two, plus one; the gap therefore exceeds the leaf count of its branch by the number of hidden circles strictly between, and in particular by at most $N-L$. At the vertex provided by the tree lemma (Lemma 4), every branch contains at most $L-3$ leaves, so every gap is at most $(L-3)+(N-L)=N-3$. (When no circle is hidden, this is the proof of Theorem 1 verbatim.)

Case 2: exactly four circles contribute arcs. The tree lemma, which requires at least five leaves, has nothing to offer here, and we locate the vertex by hand. Since the circles of $A$ and the two circles of $B$ next to the gap edges all contribute, four contributors force $|A|=2$ and leave no contributor besides these four; the hidden circles thus form the single run strictly between the two contributing circles of $B$, say $C_{p}$ and $C_{q}$ with $q-p=|B|-1=N-3$. By Lemma 8, the arcs of $C_{p}$ and $C_{q}$ are adjacent on $\partial\mathfrak{F}_{\ast}$; the edge of $\mathfrak{M}$ emanating from the corner between them terminates at a non-leaf vertex $I$, the tree $\mathfrak{M}$ having four leaves and hence not being a single edge, and $I$ touches $C_{p}$, $C_{q}$, and one or both circles of $A$. The gaps of $I$ are therefore $q-p=N-3$ together with two or three further gaps summing to $3$, and since $N\geq 5$, all of them are at most $N-3$.

In either case we obtain a vertex all of whose gaps satisfy $g_{j}\leq N-3$; add the circle bounding its maximal disk. The river remains realizable. Its course may be taken to run along the strip of width $w$ swept along the free-side boundary of the union $\bigcup_{C_{i}\in B}D_{i}$, from the gap on $\overline{v_{a}v_{a+1}}$ to the gap on $\overline{v_{b}v_{b+1}}$; this strip is disjoint from the disks of $A$ and from the added circle, since both keep distance at least $w$ from every disk of $B$, and it lies inside $P$, squeezed between $\bigcup_{C_{i}\in B}D_{i}$ and the free region. Finally, subdividing along the segments from the vertex to the centers of the touched circles decomposes $P$, exactly as in Lemma 5, into polygons with $g_{j}+2\leq N-1$ sides; each is again a polygon of touching circles, either plain (if its boundary chain stays within one bank together with the added circle) or carrying the river across it (if its chain contains circles of both banks, or a tangency across the river). ∎

Remark 1.

The two banks yield, in general, two genuinely different reductions of the same configuration, as shown in Figure 4. In a design context this freedom can be used to place the added flap on whichever side of the river is more convenient.

7 Polygons with several rivers

A circle-packed design may send several rivers through the same axial polygon. Since the courses of distinct rivers are disjoint strips, the separations they induce on the circles do not cross. The rivers thus form a laminar family, reflecting the tree structure of the underlying uniaxial base.

Definition 4.

An $N$-gon of touching circles with rivers consists of

• a simple polygon $P$ with vertices $v_{1},\dots,v_{N}$;

• circles $C_{i}$ centered at $v_{i}$ with radii $r_{i}>0$;

• a finite, possibly empty set of markers—formal points, each placed between two cyclically consecutive circles and regarded as lying on the edge of $P$ that joins their centers, so that circles and markers together form a single cyclic sequence; and

• a finite nonempty collection $\mathcal{R}$ of rivers.

Each river $R\in\mathcal{R}$ carries a width $w_{R}>0$ and a partition of the circles and markers into two banks, each a cyclically consecutive stretch of the sequence containing at least two circles; the river separates two circles or markers if they lie on different banks of $R$, and crosses the two edges of $P$ on which the sequence passes from one bank to the other. We require that no two rivers cross, in the sense that for any $R\neq R^{\prime}$, some bank of $R$ is properly contained in some bank of $R^{\prime}$; taking complements, the other bank of $R^{\prime}$ is then properly contained in the other bank of $R$, so the containments come in a complementary pair and the condition is symmetric in $R$ and $R^{\prime}$. Writing

$$\sigma_{ij}\;=\;\sum\,\bigl\{\,w_{R}:R\in\mathcal{R}\text{ separates }C_{i}\text{ from }C_{j}\,\bigr\}$$ (7–1)

for the total width separating two circles, and $w_{i}=\sigma_{i,i+1}$ for the total width crossing the edge $\overline{v_{i}v_{i+1}}$, we require further that

1. $\lvert\overline{v_{i}v_{i+1}}\rvert=r_{i}+r_{i+1}+w_{i}$ for all $i$; and

2. $\lvert\overline{v_{i}v_{j}}\rvert>r_{i}+r_{j}+\sigma_{ij}$ for all non-consecutive pairs $i,j$.

Definition 3 is the case of a single river and no markers. Note that $\sigma$ satisfies the triangle inequality $\sigma_{ij}\leq\sigma_{ik}+\sigma_{kj}$, since a river separating $C_{i}$ from $C_{j}$ separates $C_{k}$ from one of them.

The markers carry almost no geometry—an edge but no exact position on it, no width, and no mention in the two conditions. Their role is to keep parallel rivers apart. Two rivers running side by side with no circle between them would carry the same partition of the circles, and no partition of the circles alone can record which of the two strips runs first; the proper containments of Definition 4 forbid such a pair, and a marker placed between the two rivers—on one of the two edges that both of them cross—restores the proper containments and records the order. This costs no generality, as a design provides such a point in every gap between neighboring strips (Figure 6), and nothing prevents marking them all.

Figure 6: A $9$-gon of touching circles with five rivers, drawn as a designer would conceive them. The two parallel rivers at the lower left carry the same partition of the circles, and only the markers between them tell the two apart. The small black dots are the markers, one in each gap between neighboring strips on an edge. Of the remaining three rivers, the one around the right group of two circles and the one around the upper group have disjoint banks, and both banks are properly contained in the bank of the long river enclosing them both. The rivers cut the polygon into six regions, one for each face (Lemma 11); the region bounded by the latter three rivers contains no circle, and its three markers alone locate it in the cyclic sequence.

The rivers divide the polygon into regions, and the added circle will be sought in one of them. A region is recorded combinatorially by naming, for each river $R$, the bank $B_{R}$ on its far side, as seen from the region. Accordingly, a face of $\mathcal{R}$ is a choice of one bank $B_{R}$ of each river subject to the requirement that the chosen banks be pairwise nested or disjoint—a requirement most choices fail. For a region containing a circle or a marker, the choice is forced—$B_{R}$ is the bank not containing that member—and the chosen banks are automatically pairwise nested or disjoint, a common member outside two banks ruling out the crosswise containments of laminarity. The combinatorial formulation keeps track, in addition, of regions that contain neither, and frees us from carrying the courses of the rivers, which are not part of our data; the faces are exactly the regions of any drawing of the courses, as Lemma 11 below confirms.

Call a bank $F_{0}$ innermost if no river separates two of its members. Any bank that contains no other bank is innermost, since a river separating two of its members would, by laminarity, have a bank properly inside it.

Lemma 10.

Choosing, for each river, its bank disjoint from an innermost bank $F_{0}$ yields a face of $\mathcal{R}$. In particular, faces exist.

Proof.

The choice is well defined. Indeed, no river separates two members of $F_{0}$, so each river holds $F_{0}$ within a single bank, and its other bank is the one disjoint from $F_{0}$. Now consider the chosen banks of two rivers. Both avoid the members of $F_{0}$, so the two banks do not cover all the circles and markers, which rules out the crosswise containments of laminarity—the complement of one chosen bank properly inside the other; the containment that laminarity does provide then makes the two banks nested or disjoint. ∎

In the language of the circle/river method, the faces are the regions of the design visible within the polygon, and the innermost banks give the regions at the leaves of its tree; but a face may equally sit deep in the design. This reading of the faces as the regions is exact, and we now make it precise. A drawing of $\mathcal{R}$ places each marker at a point in the interior of its edge, and the rivers along pairwise disjoint strips—a strip being a closed topological disk, disjoint from the circles and the placed markers, which meets $\partial P$ in two arcs, one in the interior of each of the two edges its river crosses, and whose removal cuts $P$ into two pieces, each containing one bank, circles and markers alike. The regions of the drawing are the connected components of the complement of the strips in $P$.

Lemma 11.

In any drawing of $\mathcal{R}$, sending a region to the banks beyond its strips—for each river, the bank cut off from the region by the strip of that river—is a bijection between the regions of the drawing and the faces of $\mathcal{R}$.

Proof.

Consider first the regions. Draw the strips one at a time. Each strip is connected and disjoint from the strips drawn before it, so it lies in a single region of those, a topological disk whose boundary the strip meets in its two arcs on $\partial P$; the strip therefore cuts that region into exactly two regions, again disks. Hence the regions number $|\mathcal{R}|+1$ once all the strips are drawn, and any two distinct regions lie on opposite sides of at least one strip—the one whose drawing first put them in different regions.

Next we check that the assignment of banks lands in the faces, and is injective. Fix a region and, for each river $R$, write $P_{R}$ for the piece of $P$ beyond the strip of $R$, so that the assigned bank $B_{R}$ is the one inside $P_{R}$. Given two rivers $R\neq R^{\prime}$, the strip of $R^{\prime}$ is connected and disjoint from the strip of $R$, so it lies in $P_{R}$ or in the other piece. If it lies in $P_{R}$, then the other piece is connected, avoids the strip of $R^{\prime}$, and contains the region, so it lies in the piece of $P$ on the region’s side of $R^{\prime}$; passing to complements, $P_{R^{\prime}}$ is covered by $P_{R}$ together with the strip of $R$, and $B_{R^{\prime}}\subseteq B_{R}$ since circles and markers avoid strips. If instead the strip of $R^{\prime}$ avoids $P_{R}$, then $P_{R}$, being connected, lies either in $P_{R^{\prime}}$, giving $B_{R}\subseteq B_{R^{\prime}}$, or in the piece on the region’s side of $R^{\prime}$, giving $B_{R}\cap B_{R^{\prime}}=\emptyset$. The assigned banks are thus pairwise nested or disjoint, and the assignment is a face. It is also injective, since two regions on opposite sides of the strip of some river are assigned the two different banks of that river.

It remains to show that the faces, too, number exactly $|\mathcal{R}|+1$; this part is purely combinatorial and makes no reference to the drawing. We argue by induction on the number of rivers, a single river having exactly two faces. Suppose $|\mathcal{R}|\geq 2$. Among all banks of all rivers, let $X_{0}$ be one minimal with respect to inclusion, let $R_{0}$ be its river, and put $\mathcal{R}^{\prime}=\mathcal{R}\setminus\{R_{0}\}$. Discarding the bank chosen for $R_{0}$ turns every face of $\mathcal{R}$ into a face of $\mathcal{R}^{\prime}$, so it suffices to count, for each face of $\mathcal{R}^{\prime}$, its extensions back to $\mathcal{R}$.

Consider a river $R\neq R_{0}$. Neither bank of $R$ is contained in $X_{0}$—a proper containment would contradict the minimality of $X_{0}$, and equality would make $R$ and $R_{0}$ carry the same partition, leaving no proper containment between their banks—so, by laminarity, $X_{0}$ is contained in one bank of $R$ and disjoint from the other. In particular, whichever bank a face of $\mathcal{R}^{\prime}$ chooses for a river, the chosen bank is nested with or disjoint from $X_{0}$, and every face of $\mathcal{R}^{\prime}$ extends to a face of $\mathcal{R}$ by the choice $B_{R_{0}}=X_{0}$.

Now let a face of $\mathcal{R}^{\prime}$, with chosen banks $B_{R}$, extend instead by the choice $B_{R_{0}}=X_{0}^{\mathrm{c}}$. Of the three ways a bank $B_{R}$ can be compatible with $X_{0}^{\mathrm{c}}$, two are ruled out by the preceding paragraph—$B_{R}$ disjoint from $X_{0}^{\mathrm{c}}$ would put $B_{R}$ inside $X_{0}$, and $X_{0}^{\mathrm{c}}\subseteq B_{R}$ would put $B_{R}^{\mathrm{c}}$ there—leaving $B_{R}\subseteq X_{0}^{\mathrm{c}}$. Every river other than $R_{0}$ must therefore choose its bank disjoint from $X_{0}$, which determines the face completely; and this assignment is indeed a face, being the choice of Lemma 10 for $F_{0}=X_{0}$, a bank innermost by minimality. Hence exactly one face of $\mathcal{R}^{\prime}$ extends by $X_{0}^{\mathrm{c}}$, and the faces of $\mathcal{R}$ number $(|\mathcal{R}^{\prime}|+1)+1=|\mathcal{R}|+1$ in total. An injection between finite sets of the same size is a bijection, which proves the lemma. ∎

Fix a face of $\mathcal{R}$, with chosen banks $B_{R}$, and set

$$W_{i}\;=\;\sum\,\bigl\{\,w_{R}:C_{i}\in B_{R}\,\bigr\},$$ (7–2)

the total width of the rivers separating $C_{i}$ from the face. The set $F=\{\,C_{i}:W_{i}=0\,\}$ of the circles lying on the face may consist of several cyclic runs, or be empty; no river separates two of its circles, since a chosen bank contains neither. For a circle $C$ with center $p\in\operatorname{int}P$ and radius $\rho>0$, we say that $C$ can be added on the face if

$$d_{i}(p)\;\geq\;\rho+W_{i}\quad\text{for all }i,$$ (7–3)

and that it touches $C_{i}$—directly if $W_{i}=0$, across the rivers separating $C_{i}$ from the face if $W_{i}>0$—when equality holds; in the latter case the segment $\overline{pv_{i}}$ has length $\rho+W_{i}+r_{i}$, matching the combined width of the rivers crossing it. Subdividing along the segments from $p$ to the touched centers then decomposes $P$ as in Lemma 5, with the count of (2–2) unchanged.

Definition 4 requires both banks of every river to contain at least two circles. This loses no generality. A river $R$ whose one bank would contain a single circle $C_{i}$ can be collapsed into it, enlarging $r_{i}$ by $w_{R}$ and deleting $R$ while keeping all the markers, which decreases $\sigma_{ij}$ by exactly $w_{R}$ for every $j\neq i$ and hence preserves both conditions of the definition; moreover, every face of the collapsed family is also a face of the original one, completed by choosing for $B_{R}$ the bank of $C_{i}$—by laminarity some bank of $R$ is properly contained in some bank of any other river, and it must be the bank of $C_{i}$, no bank holding two circles fitting inside it; the bank of $C_{i}$ is thus contained in one bank, hence contained in or disjoint from each bank, of every other river—with the same widths $W_{j}$ for $j\neq i$, while $d_{i}$ and $W_{i}$ decrease by the same amount $w_{R}$, so the circles that can be added on the face, and the circles they touch, are unchanged. This normalization is needed when the subdivision below is iterated, as a subdivided part may retain only one circle of some bank.

Theorem 4.

For any $N$-gon of touching circles with rivers, with $N>4$, and any face of $\mathcal{R}$, it is possible to add a circle on that face, touching at least three of the circles—directly or across the rivers—so that the largest reduced polygon has, at most, $N-1$ sides.

The proof retraces Section 6. The rivers are absorbed into the circles, and the medial axis of what remains of the free region provides the added circle. The new difficulty is that the total expansions $W_{i}$ differ from circle to circle, and a disk expanding past a slower, already halted one could plough through it and emit new free boundary, which the monotonicity argument of Lemma 8 cannot tolerate. The remedy is to absorb the rivers one at a time, innermost first. Then all disks in motion expand at a common unit rate at every moment, and we will see that they touch nothing else. We emphasize that the induction implicit in this staging is structural induction along a forest of rivers, defined below—equivalently, on its height—and not on the number of rivers. Absorbing a river does not produce a smaller instance of Definition 4, since the expanded circles of its bank overlap, so no statement about configurations with fewer rivers is ever available; what is propagated from stage to stage is instead the boundary invariant of Lemma 14 below. The four absorption lemmas of this section extend those of Section 6 one for one—Lemmas 12 and 13 generalize the two parts of Lemma 7, Lemma 14 generalizes Lemma 8, and Lemma 15 generalizes Lemma 9—and each pair coincides when the river is single; the reader may lean on the correspondence throughout.

The order of absorption is governed by a forest. The chosen banks are pairwise nested or disjoint; ordered by inclusion of these sets, the rivers thus form a forest of rooted trees, one for each maximal chosen bank, which we call the river forest of the face, with $R^{\prime}$ a descendant of $R$ when $B_{R^{\prime}}\subseteq B_{R}$ (parallel rivers, with equal banks, may be arranged in a chain arbitrarily); in the language of the circle/river method, this is the tree of the underlying base, rooted at the region of the face. Now order the rivers as $R_{1},\dots,R_{K}$ so that every river comes after its descendants, that is, $B_{R_{k}}\subsetneq B_{R_{l}}$ implies $k<l$—for instance, by peeling the leaves of the river tree round after round—and abbreviate $B_{k}=B_{R_{k}}$, $w_{k}=w_{R_{k}}$. The choice of order gives the property used throughout:

$$\text{for }l<k:\qquad B_{l}\subseteq B_{k}\quad\text{or}\quad B_{l}\cap B_{k}=\emptyset.$$ (7–4)

Let $\tau_{k}=w_{1}+\cdots+w_{k}$, and call the time interval $[\tau_{k-1},\tau_{k}]$ stage $k$. During stage $k$ exactly the circles of $B_{k}$ expand, at unit rate. Thus for $t=\tau_{k-1}+s$ with $s\in[0,w_{k}]$,

$$\tilde{r}_{i}(t)\;=\;r_{i}+a_{i}(t),\qquad a_{i}(t)\;=\;\sum_{l<k,\ C_{i}\in B_{l}}w_{l}\;+\;s\,[\,C_{i}\in B_{k}\,],$$ (7–5)

where $[\,\cdot\,]$ is the Iverson bracket, which equals $1$ if the condition holds and $0$ otherwise. At the final time $\tau_{K}$ every circle has absorbed exactly the rivers separating it from the face, so $\tilde{r}_{i}=r_{i}+W_{i}$, and by (7–3) a circle can be added on the face exactly when it can be added to this final expanded configuration in the sense of Definition 2. Let $\mathfrak{F}(t)$ denote the free region of the expanded disks, as before. On each edge $e=\overline{v_{c}v_{c+1}}$, the residual mouth at time $t$ is the set of points $q\in e$ with $\lvert\overline{qv_{c}}\rvert\geq\tilde{r}_{c}(t)$ and $\lvert\overline{qv_{c+1}}\rvert\geq\tilde{r}_{c+1}(t)$—a segment of length $w_{e}-a_{c}(t)-a_{c+1}(t)$ when this is positive, the part of the gap not yet closed.

The next two lemmas confine each stage—an expanding disk can meet neither a resting disk nor a residual mouth. Both proofs amount to bookkeeping with (7–4).

Lemma 12 (separation).

During stage $k$, at time $t=\tau_{k-1}+s$, for all $C_{j}\in B_{k}$ and $C_{m}\notin B_{k}$,

$$\lvert\overline{v_{j}v_{m}}\rvert-\tilde{r}_{j}(t)-\tilde{r}_{m}(t)\;\geq\;w_{k}-s,$$

with equality only if $C_{j},C_{m}$ are consecutive and every river crossing their edge, other than $R_{k}$, is already absorbed. In particular, an expanding disk meets a resting disk only at the very end of a stage, in a tangency of a consecutive pair.

Proof.

We claim that the rivers absorbed before stage $k$ that have expanded $C_{j}$ or $C_{m}$, together with $R_{k}$, are pairwise distinct and all separate $C_{j}$ from $C_{m}$. Distinctness is clear, since a river expands the circles of only one of its banks, and $R_{k}$ is not yet absorbed. If $R_{l}$ ($l<k$) has $C_{j}\in B_{l}$, then $B_{l}\subseteq B_{k}$ by (7–4), so $C_{m}\notin B_{l}$ and $R_{l}$ separates the pair. If $R_{l}$ has $C_{m}\in B_{l}$, then $B_{l}\subseteq B_{k}$ is impossible, so $B_{l}\cap B_{k}=\emptyset$ by (7–4), so $C_{j}\notin B_{l}$ and again $R_{l}$ separates. Finally $R_{k}$ separates, since $C_{j}\in B_{k}\not\ni C_{m}$. Consequently

$$\sigma_{jm}\;\geq\;\bigl(a_{j}(t)-s\bigr)+a_{m}(t)+w_{k},$$

and combining with $\lvert\overline{v_{j}v_{m}}\rvert\geq r_{j}+r_{m}+\sigma_{jm}$ gives the bound. For non-consecutive pairs the latter inequality is strict. For consecutive pairs it is an equality with $\sigma_{jm}=w_{e}$, the rivers separating the pair being exactly those crossing their edge $e$; equality in the bound then forces every unabsorbed river crossing $e$ other than $R_{k}$ to be absent. ∎

Lemma 13 (mouth integrity).

At no time does a disk $\tilde{D}_{j}(t)$ contain a point of the residual mouth of an edge not incident to $v_{j}$.

Proof.

Since disks never shrink and residual mouths never grow, a violation with $C_{j}$ resting entails a violation at the last prior instant at which $C_{j}$ was expanding (or at $t=0$, the start of stage $1$); so we may assume $C_{j}\in B_{k}$ during stage $k$, at time $t=\tau_{k-1}+s$. Let $q$ be a point of the residual mouth of the edge $e=\overline{v_{c}v_{c+1}}$ with $j\neq c,c+1$, and suppose $q\in\tilde{D}_{j}(t)$. We distinguish three cases by the position of the endpoints of $e$.

Both $C_{c},C_{c+1}\in B_{k}$. Then the residual mouth of $e$ is empty, a contradiction. Indeed, the bank $B_{R}$ of a river crossing $e$ contains exactly one of $C_{c},C_{c+1}$, so it neither contains $B_{k}$ nor is disjoint from it nor equals it, and, the chosen banks being pairwise nested or disjoint, $B_{R}\subsetneq B_{k}$; by the choice of order every river crossing $e$ is then absorbed, each having expanded $C_{c}$ or $C_{c+1}$, so that $a_{c}(t)+a_{c+1}(t)\geq w_{e}$.

Exactly one endpoint, say $C_{c}$, lies in $B_{k}$ (so that $R_{k}$ crosses $e$). Using $\lvert\overline{qv_{c}}\rvert\geq\tilde{r}_{c}(t)$,

$$\lvert\overline{v_{j}v_{c+1}}\rvert\leq\lvert\overline{v_{j}q}\rvert+\lvert\overline{qv_{c+1}}\rvert\leq\tilde{r}_{j}(t)+\lvert\overline{v_{c}v_{c+1}}\rvert-\tilde{r}_{c}(t)=r_{j}+r_{c+1}+a_{j}(t)+w_{e}-a_{c}(t).$$

We claim that $\sigma_{j,c+1}\geq a_{j}(t)+w_{e}-a_{c}(t)$; note that the two current-stage contributions $s$ cancel here, as both $C_{j}$ and $C_{c}$ lie in $B_{k}$. Granting the claim, the display contradicts Definition 4(2) if $C_{j},C_{c+1}$ are non-consecutive. If they are consecutive ($j=c+2$), the display and the claim force equality throughout; in particular $q$ lies on the segment $\overline{v_{c+2}v_{c+1}}$, and so on two distinct edges of $P$—its own edge $e$ and this one—which meet only at their shared vertex; thus $q=v_{c+1}$, impossible for a point of the residual mouth, as $\tilde{r}_{c+1}>0$. To verify the claim, say that a river has expanded $C_{i}$ if it is already absorbed with $C_{i}$ in its bank $B$; we check that each river $S\in\mathcal{R}$ contributes to the right-hand side of the claim at most what it contributes to $\sigma_{j,c+1}$, i.e., that

$$[S\text{ has expanded }C_{j}]+[S\text{ crosses }e]-[S\text{ has expanded }C_{c}]\leq[S\text{ separates }C_{j},C_{c+1}].$$

Only the cases with positive left-hand side need checking; all use (7–4) and $C_{c+1}\notin B_{k}$. If $S$ has expanded $C_{j}$, then $B_{S}\subseteq B_{k}$, so $C_{c+1}\notin B_{S}$ and $S$ separates $C_{j}$ from $C_{c+1}$; moreover, if such an $S$ crosses $e$, then the endpoint it contains must be $C_{c}$, and the left-hand side is again $1$. If $S$ crosses $e$ and has not expanded $C_{j}$, then either $C_{c+1}\in B_{S}$, in which case $B_{S}$ is neither nested with $B_{k}$ (it misses $C_{c}\in B_{k}$ and contains $C_{c+1}\notin B_{k}$)—so it is disjoint from $B_{k}$, misses $C_{j}$, and $S$ separates; or $C_{c}\in B_{S}$, in which case $B_{S}\subsetneq B_{k}$ would mean that $S$ has expanded $C_{c}$ (left-hand side $\leq 0$), so $B_{S}\supseteq B_{k}$, the chosen banks being pairwise nested or disjoint, so $C_{j}\in B_{S}\not\ni C_{c+1}$ and $S$ separates.

Neither endpoint lies in $B_{k}$. Then $R_{k}$ does not cross $e$ and separates $C_{j}$ from both endpoints; so does every river absorbed with $C_{j}$ in its bank, whose bank is contained in $B_{k}$ by (7–4) and therefore avoids $C_{c},C_{c+1}$. Since, moreover, every river crossing $e$ separates $C_{j}$ from exactly one endpoint,

$$\sigma_{jc}+\sigma_{j,c+1}\;\geq\;2\bigl(a_{j}(t)-s\bigr)+2w_{k}+w_{e}\;\geq\;2a_{j}(t)+w_{e}.$$

On the other hand, adding the triangle estimates through the two endpoints and using $\lvert\overline{qv_{c}}\rvert+\lvert\overline{qv_{c+1}}\rvert=\lvert\overline{v_{c}v_{c+1}}\rvert=r_{c}+r_{c+1}+w_{e}$,

$$2\lvert\overline{v_{j}q}\rvert\;\geq\;\lvert\overline{v_{j}v_{c}}\rvert+\lvert\overline{v_{j}v_{c+1}}\rvert-r_{c}-r_{c+1}-w_{e}\;\geq\;2r_{j}+\sigma_{jc}+\sigma_{j,c+1}-w_{e}\;\geq\;2\tilde{r}_{j}(t),$$

where the middle inequality is strict because $C_{j}$ cannot be consecutive to both endpoints. Hence $q\notin\tilde{D}_{j}(t)$. ∎

With the stages thus insulated, the shrinking lemma extends.

Lemma 14 (shrinking, staged).

For every $t\in[0,\tau_{K}]$, each connected component of $\mathfrak{F}(t)$ is bounded by circular arcs of distinct circles—at most one arc per circle—occurring along the boundary in their cyclic index order, interleaved in the correct positions with residual mouth segments, at most one per edge.

Proof.

At $t=0$ the proofs of Lemmas 1 and 2 apply verbatim except on the edges with $w_{e}>0$, where the mouths appear. Thus $\mathfrak{F}(0)$ is a single component bounded by the $N$ arcs in cyclic order and the initial mouths. We show that this structure can only degenerate, never reorganize.

First, death is permanent, across all stages. Fix $C_{j}$ and a unit vector $u$, and follow the point $p(t)$ with $\mathchoice{\overarrow@\to{p}}{\overarrow@\to{p}}{\overarrow@\to{p}}{\overarrow@\to{p}}(t)=\mathchoice{\overarrow@\to{v_{j}}}{\overarrow@\to{v_{j}}}{\overarrow@\to{v_{j}}}{\overarrow@\to{v_{j}}}+\tilde{r}_{j}(t)\,u$, which moves, at unit speed, exactly while $C_{j}$ expands. Suppose $p(t_{0})\in\tilde{D}_{m}(t_{0})$ for some $m\neq j$, and take $t_{0}$ minimal. At $t_{0}$, at least one of $C_{j}$ and $C_{m}$ is expanding, for otherwise both $p$ and $\tilde{D}_{m}$ would be stationary just before $t_{0}$, contradicting the minimality of $t_{0}$. In fact both are expanding, since the point $p(t_{0})$ lies in $\tilde{D}_{j}(t_{0})\cap\tilde{D}_{m}(t_{0})$, and by Lemma 12 an expanding disk meets no resting disk. So $C_{j},C_{m}\in B_{k}$ for the current stage $k$. At any later time at which $C_{j}$ expands, during a stage $l\geq k$ with $C_{j}\in B_{l}$, property (7–4) gives $B_{k}\subseteq B_{l}$, so $C_{m}$ expands as well; therefore $\lvert\overline{p(t)\,v_{m}}\rvert\leq\tilde{r}_{m}(t)$ persists exactly as in the proof of Lemma 8—while both circles expand, $p$ moves with unit speed and $\tilde{D}_{m}$ grows with unit speed, and while $C_{j}$ rests, $p$ is stationary and disks never shrink. If instead $p(t_{0})$ exits $P$, then at the first later return of $p$ to $\partial P$ the return point lies on an edge and on no residual mouth (it lies on $\tilde{C}_{j}\subset\tilde{D}_{j}$, and Lemma 13 applies, the incident edges being met only along themselves), and is therefore within $\tilde{r}_{c}$ of an endpoint $v_{c}$ of its edge, and we are back in the previous case, with $\tilde{D}_{c}$ as the covering disk. Hence every boundary arc—viewed as the set of directions $u$ it spans, its radius never decreasing—can only shrink, split, or vanish, and no circle ever contributes new boundary material; mouths likewise only recede, their endpoints advancing with the expanding end disks, unreachable by all other disks.

Second, the combinatorial structure changes only at finitely many critical times, namely when an arc or mouth degenerates to a point, or when two expanded circles become tangent at a point of the closure of the free region. By Lemma 12 such a tangency involves two co-expanding circles, or a consecutive pair at the end of a stage, where their residual mouth closes into a cusp. A visible tangency point of two co-expanding circles lies in the interior of $P$; on $\partial P$ it would be a covered edge point, invisible, or a point of a residual mouth, excluded by Lemma 13. The pinching argument of Lemma 8 then applies verbatim—the component splits, and each part inherits a contiguous run of the boundary sequence. In all cases the invariant survives, and the lemma follows by induction over the critical times; the transitions between stages are not events, the radii being continuous. ∎

Lemma 15.

Let $M_{1},\dots,M_{d}$ be the maximal chosen banks (pairwise disjoint), call the edges joining a circle of some $M_{a}$ to a circle outside it the junction edges, and call the two circles of $M_{a}$ adjacent to its two junction edges its extremes. At $t=\tau_{K}$, every junction edge carries a tangency cusp of its two endpoint disks, and some component $\mathfrak{F}_{\ast}$ of $\mathfrak{F}(\tau_{K})$ carries on its boundary all the arcs of the circles of $F$, all the junction cusps, and, for each $M_{a}$, arcs of both of its extremes.

Proof.

Throughout the proof we use the following strict separation. For $C_{i}\in M:=M_{a}$ and $C_{m}\notin M$, every river whose chosen bank contains $C_{i}$ or $C_{m}$ separates the pair—in the first case the chosen bank is nested into $M$, which avoids $C_{m}$; in the second it can neither contain nor equal the maximal bank $M$, so it is disjoint from it and avoids $C_{i}$—so $\sigma_{im}\geq W_{i}+W_{m}$ and, at every time,

$$\lvert\overline{v_{i}v_{m}}\rvert-\tilde{r}_{i}-\tilde{r}_{m}\;\geq\;\sigma_{im}-W_{i}-W_{m}\;\geq\;0,$$

strictly for non-consecutive pairs. In particular, the disks of $M$ never meet the disks of the other maximal banks, nor those of the circles of $F$, except that a consecutive pair across a junction edge may become tangent.

Cusps. Let $e=\overline{v_{c}v_{c+1}}$ be a junction edge, say $C_{c+1}\in M$ and $C_{c}\notin M$. A chosen bank containing $C_{c+1}$ is a subinterval of $M$ containing its extreme $C_{c+1}$, so $e$ is one of its two boundary edges and its river crosses $e$; likewise, a chosen bank containing $C_{c}$ is a subinterval, with extreme $C_{c}$, of the maximal bank on the other side (if $C_{c}\in F$ there is none). Hence every river that ever expands $C_{c}$ or $C_{c+1}$ crosses $e$; consequently $W_{c}+W_{c+1}=w_{e}$, the residual mouth of $e$ has, at every time, length equal to the total width of its unabsorbed rivers, and it closes into a tangency of $\tilde{D}_{c}$ and $\tilde{D}_{c+1}$ exactly when the last of them is absorbed—after which neither endpoint circle ever expands again, so the tangency persists to $\tau_{K}$. Its cusp point stays on the boundary of the free region. It is a limit of points of the residual mouth, and a closed disk containing no point of a residual mouth contains no limit of such points (Lemma 13).

Fronts. The goal of this step is to show that each maximal bank presents a single connected front to the face—the union of its expanded disks borders the free region along one chain of free arcs, running from the cusp on one of its junction edges to the cusp on the other—so that, in particular, both extremes of the bank contribute arcs. Fix $M=M_{a}$, let $x,x^{\prime}$ be the cusps on its two junction edges, and let

$$Y\;=\;\bigcup_{C_{i}\in M}\bigl(\tilde{D}_{i}(\tau_{K})\cap\overline{P}\bigr).$$

First, $Y$ is connected. For consecutive circles of $M$, the point of their edge at distance $\tilde{r}_{c}$ from $v_{c}$ lies in both disks, since every river crossing an edge within $M$ is absorbed (its chosen bank, containing one endpoint, is a proper subinterval of $M$); so the sets $\tilde{D}_{i}\cap\overline{P}$, $C_{i}\in M$, chain up through their edges. And every point $y\in\tilde{D}_{i}\cap\overline{P}$ joins this chain within $Y$. If the segment $\overline{yv_{i}}\subset\tilde{D}_{i}$ leaves $P$, then, walking from $y$ toward $v_{i}$, its first crossing $z$ of $\partial P$ lies on an edge, in $\tilde{D}_{i}$; either that edge is incident to $v_{i}$ and the piece of it from $z$ to $v_{i}$ lies in $\tilde{D}_{i}\cap\overline{P}$, or $z$ lies on no residual mouth (Lemma 13) and is therefore covered by an endpoint disk $\tilde{D}_{c}$ of its edge, with $C_{c}\in M$ by strict separation, and the piece of the edge from $z$ to $v_{c}$ lies in $\tilde{D}_{c}\cap\overline{P}$.

Second, $Y\cap\partial P$ is the closed stretch of $\partial P$ from $x$ to $x^{\prime}$ behind $M$. It contains the covered parts of the two junction edges up to their cusps, the edges within $M$ (whose mouths are closed, as above), and the centers of the circles of $M$; conversely, no disk of $M$ contains the center of another circle (by strict separation, $\lvert\overline{v_{i}v_{m}}\rvert\geq\tilde{r}_{i}+\tilde{r}_{m}>\tilde{r}_{i}$), nor a point of an edge joining two circles outside $M$—such a point lies on a residual mouth, excluded by Lemma 13, or is covered by an endpoint disk, which the disks of $M$ avoid, junction pairs touching only at their cusps, on their own edges.

Now let $V$ be the component of $\overline{P}\setminus Y$ containing the complementary stretch $\partial P\setminus(Y\cap\partial P)$, which is connected. The set $\overline{P}\setminus V$ is closed and connected, being the union of $Y$ with the remaining components of $\overline{P}\setminus Y$, the closure of each of which meets $Y$. Since $\overline{P}$ is homeomorphic to a closed disk, it is unicoherent: whenever it is written as the union of two closed connected sets, their intersection is connected [Kuratowski 68, §57]. Applied to $\overline{V}$ and $\overline{P}\setminus V$, whose intersection is the frontier of $V$, this shows that frontier to be connected. This frontier contains $x$ and $x^{\prime}$, lies in $Y$, and meets $\partial P$ only at these two points; elsewhere it consists of points of the circles $\tilde{C}_{i}$, $C_{i}\in M$, interior to $P$, interior to no disk of $M$ (they lie on the boundary of $Y$) and to no other expanded disk (strict separation)—that is, of free boundary arcs of the circles of $M$, which near $x$ and $x^{\prime}$ run along the disks of the two extremes.

Assembly. The circles of $F$ never expand, and no expanded disk ever meets their disks or arcs (strict separation, applied to the maximal bank of the expanded circle). The free points at sufficiently small positive distance from the arcs of the circles of $F$ and from the fronts just constructed form a connected set. Within each cyclic run of $F$, the collar passes through the interior wedges at the tangency cusps of the run, as in Lemma 9; and at each junction cusp, the interior wedge between the two tangent disks joins the collars or fronts on its two sides. Hence all of these free points lie in a single component $\mathfrak{F}_{\ast}$ of $\mathfrak{F}(\tau_{K})$, whose boundary carries the arcs of all circles of $F$, every junction cusp, and arcs of both extremes of every maximal bank. ∎

Proof of Theorem 4.

Let $\mathfrak{F}_{\ast}$ be the component of Lemma 15 and $\mathfrak{M}=\mathfrak{M}(\mathfrak{F}_{\ast})$. By Lemma 14, $\partial\mathfrak{F}_{\ast}$ consists of arcs of distinct circles in cyclic index order, meeting at corners which are tangency cusps or transversal crossings. No residual mouth segment survives at $\tau_{K}$. An edge joining two circles of $F$ is crossed by no river; a junction edge has closed into its cusp (Lemma 15); and every other edge joins two circles of the same maximal bank, so all the rivers crossing it are absorbed—their chosen banks being proper subintervals—each absorption expanding an endpoint circle of the edge, so that $a_{c}+a_{c+1}\geq w_{e}$ in the end. Crossings are indeed transversal, no two of the final circles being nested:

$$|\tilde{r}_{i}-\tilde{r}_{j}|\;\leq\;|r_{i}-r_{j}|+|W_{i}-W_{j}|\;<\;r_{i}+r_{j}+\sigma_{ij}\;\leq\;\lvert\overline{v_{i}v_{j}}\rvert,$$

using $|W_{i}-W_{j}|\leq\sigma_{ij}$, which holds because the rivers counted in one of $W_{i},W_{j}$ but not the other separate $C_{i}$ from $C_{j}$. All corners are therefore sharp, $\mathfrak{F}_{\ast}$ is a simply connected domain of the class of Theorem 2, and the analysis of Lemma 3 applies with the modifications noted in the proof of Theorem 3. Thus $\mathfrak{M}$ is a finite tree whose leaves are the corners of $\partial\mathfrak{F}_{\ast}$, and every non-leaf vertex, of degree $k$, is the center of a maximal disk touching exactly $k$ of the final circles, with $d_{i}(p)=\rho+W_{i}$ at the touched circles and $d_{i}(p)\geq\rho+W_{i}$ at all others—by (7–3), a circle that can be added on the face, touching the corresponding circles directly or across the rivers.

The two cases of the proof of Theorem 3 now go through with $F$ in place of the bank $A$. Here the circles of $F$ and the two extremes of every maximal bank are never hidden (Lemma 15), and these number at least four—if there is a single maximal bank, then $F$ contains the other bank of its river, which has at least two circles. When at least five circles contribute arcs, the first case applies verbatim, its accounting of gaps against leaves making no reference to the banks. When exactly four circles contribute, the hidden circles need no longer form a single run. They do lie in the interiors of the maximal banks, everything else—the circles of $F$ and the extremes—being never hidden, and four contributors leave room for the extremes of at most two maximal banks; the hidden circles therefore fill at most two runs. So we take instead the corner between the two contributing circles enclosing a largest hidden run, of $h\geq 1$ circles, and the non-leaf vertex $I$ reached from it. The gap of $I$ through that run is $h+1\leq N-3$, and every other branch of $I$ contains at most two of the remaining leaves and at most the remaining $N-4-h$ hidden circles, so every other gap is at most $2+(N-4-h)\leq N-3$.

It remains to check that the subdivision is valid and that the rivers remain realizable. For the subdivision, the segment from $p$ to a touched center $v_{i}$ passes through the contact point $q_{i}$, and $\overline{pq_{i}}\subset\mathcal{D}_{p}\subseteq\mathfrak{F}_{\ast}\subseteq P$; the remaining piece $\overline{q_{i}v_{i}}$ is the radius of $\tilde{D}_{i}$ in the direction of $q_{i}$, and lies in $P$. Since $q_{i}$ is a free boundary point at the final time, the point $p(t)$ of its direction never left $P$—a direction that exits $P$ is dead forever by the proof of Lemma 14—so the radius from $v_{i}+r_{i}u$ outward is swept by $p(t)$ within $P$, while the initial piece inside the original disk $D_{i}$ is a radial segment of the sector $D_{i}\cap P$ of Lemma 2(3), whose proof applies to the initial configuration verbatim. The segments therefore subdivide $P$ as in Lemma 5, into polygons with $g_{j}+2\leq N-1$ sides. Each reduced polygon, endowed with the markers on its own edges and the rivers of $\mathcal{R}$ that separate two of its circles—the added circle $C$ counting as lying on the face, so that a river separates $C$ from $C_{i}$ exactly when $C_{i}\in B_{R}$, and a river left with a single circle of the part on one side being collapsed into it as described after (7–3)—is again a polygon of touching circles with rivers (or without, when no river survives); its new edges have length $\rho+r_{i}+W_{i}$, matching condition (1), since the rivers crossing the new edge $\overline{pv_{i}}$ are exactly those separating $C_{i}$ from the face; condition (2) is inherited, and so is laminarity—restriction to the part preserves every containment, and where it turns a proper containment into an equality, everything telling the two rivers apart having fallen to the other parts, a fresh marker inserted between them, in the order of their original nesting, restores it. Finally, the rivers can be rerouted stage by stage. The course of $R_{k}$ may be taken to run along the strip swept during stage $k$ by the free-side boundary of $\bigcup_{i}\tilde{D}_{i}(t)$, a strip of width $w_{k}$ entering and leaving $P$ through the residual mouths of the two edges crossed by $R_{k}$, which recede at unit rate during exactly this stage. These strips are pairwise disjoint, the union of the disks being nondecreasing and the time windows disjoint; each separates precisely the circles of $B_{k}$ from the others; they avoid the disks of $F$ (Lemma 12) and keep distance at least $\rho$ from the added circle, since $d_{i}(p)\geq\rho+W_{i}\geq\rho+a_{i}(t)$ for all $i$ and $t$. ∎

Corollary 4.1.

Every $N$-gon of touching circles with rivers can be subdivided into triangles and quadrilaterals by adding at most $N-4$ circles.

Proof.

The induction of Corollary 2.1 applies verbatim, using Theorem 4 (with any face of the inherited river family) in place of Theorem 1 for the parts crossed by rivers. ∎

Remark 2.

Theorem 4 generalizes the freedom of choice of Theorem 3. The designer may place the added flap in any region of the design visible within the polygon—in a leaf group of flaps, between rivers, or even in a region carrying no flap at all, such as the central region enclosed by three rivers whose far banks are pairwise disjoint—one appears in Figure 6—in which case every touch of the added circle is across a river.

8 Concluding remarks

We have shown that in any axial polygon of a circle-packed design with more than four sides, a circle can always be added so that every reduced polygon is strictly smaller, and consequently that at most $N-4$ added circles reduce an $N$-gon entirely into triangles and quadrilaterals—for which classical geometric molecule constructions exist. The proof identifies the candidate circles with the internal vertices of the medial axis of the free region, a tree whose combinatorics alone guarantee the existence of a good vertex; the same skeleton, computed as an Apollonius diagram, serves as a practical algorithm for finding the added circle.

Several questions remain open.

1. Minimum number of additions. The bound of $N-4$ added circles is sharp in the worst case (Corollary 2.2), but an individual configuration may admit a much shorter subdivision—a single circle touching many others can reduce an $N$-gon to triangles at one stroke. Our algorithm only guarantees a decrease of the order at each step and does not compute the minimum; characterizing it, or computing it efficiently, is open.

2. Other objectives. From the design point of view, each added circle is an extra flap, so one may prefer to minimize quantities other than their number—the total radius of the added circles (the total length of extra material), the largest added radius, or a subdivision using only radii from a prescribed range. Nothing is known about these constrained versions, including whether they are computationally tractable.

3. Quality of the molecules. The interplay between the choice of the added circle and the shape of the resulting molecules—for instance, the aspect ratios of the triangles and quadrilaterals produced—is a natural direction for further study, as thin polygons yield crease patterns that are difficult to fold in practice.

Beyond these, the staged-shrinking technique of Lemmas 8 and 14 may be of independent interest for further extensions, for instance to metrics other than the Euclidean one or to more general weighted Voronoi settings.

Mu-Tsun Tsai
New Taipei City, TAIWAN, e-mail: don.m.t.tsai@gmail.com