# Chains, Koch Chains, and Point Sets with many Triangulations

Daniel Rutschmann111Department of Computer Science, ETH Zürich, Switzerland.
E-mail<EMAIL_ADDRESS>Manuel Wettstein222Department of Computer Science, ETH
Zürich, Switzerland. E-mail<EMAIL_ADDRESS>
(February 24, 2023)

###### Abstract

We introduce the abstract notion of a chain, which is a sequence of $n$ points
in the plane, ordered by $x$-coordinates, so that the edge between any two
consecutive points is unavoidable as far as triangulations are concerned. A
general theory of the structural properties of chains is developed, alongside
a general understanding of their number of triangulations.

We also describe an intriguing new and concrete configuration, which we call
the Koch chain due to its similarities to the Koch curve. A specific
construction based on Koch chains is then shown to have $\Omega(9.08^{n})$
triangulations. This is a significant improvement over the previous and long-
standing lower bound of $\Omega(8.65^{n})$ for the maximum number of
triangulations of planar point sets.

##  1 Introduction

Let $P$ be a set of $n$ points in the Euclidean plane. Throughout the paper,
$P$ is assumed to be in _general position_ , which means for us that no two
points have the same $x$-coordinate and that no three points are on a common
line. A _geometric graph_ on $P$ is a graph with vertex set $P$ combined with
an embedding into the plane where edges are realized as straight-line segments
between the corresponding endpoints. It is called _crossing-free_ if the edges
have no pairwise intersection, except possibly in a common endpoint.

#### Triangulations.

Perhaps the most prominent and most studied family of crossing-free geometric
graphs is the family of _triangulations_ , which may be defined simply as
edge-maximal crossing-free geometric graphs on $P$. It is easy to see that
such a definition implies that the edges of any triangulation subdivide the
convex hull of $P$ into triangular regions.

Let $\mathrm{tr}(P)$ denote the number of triangulations on a given point set
$P$. Trying to better understand this quantity is a fundamental question in
combinatorial and computational geometry. For very specific families of point
sets, exact formulas or at least asymptotic estimates can be derived. For
example, it is well-known that if $P$ is a set of $n$ points in _convex
position_ , then $\mathrm{tr}(P)=C_{n-2}$, where
$C_{k}=\frac{1}{k+1}\binom{2k}{k}=\Theta(k^{-3/2}4^{k})$ is the $k$-th Catalan
number [1]. In general, however, this problem turns out to be much more
elusive.

There is an elegant algorithm by Alvarez and Seidel [7] from 2013 that
computes $\mathrm{tr}(P)$ in exponential time $O(2^{n}n^{2})$. It has been
surpassed by Marx and Miltzow [16] in 2016, who showed how to compute
$\mathrm{tr}(P)$ in subexponential time $n^{O(\sqrt{n})}$. Moreover, Avis and
Fukuda [9] have shown already in 1996 how to enumerate the set of all
triangulations on $P$ (i.e., to compute an explicit representation of each
element) by using a general technique called reverse search in time
$\mathrm{tr}(P)\cdot p(n)$ for some polynomial $p$. A particularly efficient
implementation of that technique with $p(n)=O(\log\log n)$ has been described
by Bespamyatnikh [10].

Extensive research has also gone into extremal upper and lower bounds in terms
of the number of points. That is, if we define

$\displaystyle\mathrm{tr}_{\mathrm{max}}(n)=\max_{P\colon|P|=n}\mathrm{tr}(P),$
$\displaystyle\mathrm{tr}_{\mathrm{min}}(n)=\min_{P\colon|P|=n}\mathrm{tr}(P)$

to be the respectively largest and smallest numbers of triangulations
attainable by a set $P$ of $n$ points in general position, then various
authors have attempted to establish and improve upper and lower bounds on
these quantities.

As far as the maximum is concerned, a seminal result by Ajtai, Chvátal,
Newborn, and Szemerédi [6] from 1982 shows that the number of
triangulations—and, more generally, the number of all crossing-free geometric
graphs—is at most $10^{13n}$. A long series of successive improvements [23,
11, 20, 19, 22] using a variety of different techniques has culminated in the
currently best upper bound $\mathrm{tr}_{\mathrm{max}}(n)\leq 30^{n}$ due to
Sharir and Sheffer [21], which has remained uncontested for over a decade.
Coming from the other side, attempts have been made to construct point sets
with a particularly large number of triangulations. For some time, the _double
chain_ by García, Noy, and Tejel [17] with approximately $\Theta(8^{n})$
triangulations was conjectured to have the largest possible number of
triangulations. However, variants like the _double zig-zag chain_ by
Aichholzer et al. [5] with $\Theta(8.48^{n})$ triangulations and a specific
instance of the _generalized double zig-zag chain_ by Dumitrescu, Schulz,
Sheffer, and Tóth [12] with $\Omega(8.65^{n})$ triangulations have since been
discovered. But also on this front, no further progress on the lower bound
$\mathrm{tr}_{\mathrm{max}}(n)=\Omega(8.65^{n})$ has been made for a decade.

The situation for the minimum is different insofar that the _double circle_
with $\Theta(3.47^{n})$ triangulations, as analyzed by Hurtado and Noy [15] in
1997, is still conjectured by many to have the smallest number of
triangulations. In other words, it is believed that the resulting upper bound
$\mathrm{tr}_{\mathrm{min}}(n)=O(3.47^{n})$ is best possible. On the other
hand, Aichholzer et al. [4] have shown that every point set has at least
$\Omega(2.63^{n})$ triangulations, thereby establishing the lower bound
$\mathrm{tr}_{\mathrm{min}}(n)=\Omega(2.63^{n})$.

The focus of this paper lies on $\mathrm{tr}_{\mathrm{max}}(n)$ and, more
specifically, on establishing an improved lower bound on that quantity.
Ultimately, we show how to construct a new infinite family of point sets with
$\Omega(9.08^{n})$ triangulations, thereby proving
$\mathrm{tr}_{\mathrm{max}}(n)=\Omega(9.08^{n})$.

#### General chains.

It has occurred to us that almost all families of point sets whose numbers of
triangulations have been analyzed over the years have a very special
structure, which we are trying to capture in the following definition.

######  Definition 1.

A _chain_ $C$ is a sequence of points $p_{0},\dots,p_{n}$ sorted by increasing
$x$-coordinates, such that the edge $p_{i-1}p_{i}$ is _unavoidable_ (i.e.,
contained in every triangulation of $C$) for each $i=1,\dots,n$. These
specific unavoidable edges are also referred to as _chain edges_.

In contrast to previous convention, we use the parameter $n$ to denote the
number of chain edges and not the number of points in $C$, which is $n+1$.
Also note that Definition 1 implies that the edge $p_{0}p_{n}$ is an edge of
the convex hull and, hence, also unavoidable. Indeed, since all chain edges
are unavoidable, the edge $p_{0}p_{n}$ cannot possibly cross any of them and,
hence, is either above or below all the points in between. Therefore, a chain
always admits a spanning cycle of unavoidable edges with at least one hull
edge. We prove in Section 2 that this is also a characterization of chains in
terms of _order types_ (see [14] for a definition).

######  Theorem 2.

For every point set that admits a spanning cycle of unavoidable edges
including at least one convex hull edge, there exists a chain with the same
order type.

All of the mentioned families of point sets (convex position, double chain,
and so on) are usually neither defined nor depicted in a way that makes it
clear that they may be thought of as chains as in Definition 1. Still, the
premise of Theorem 2 is easily verified for all of them except for the double
circle, which may however be transformed into a chain by removing one of the
inner points. Figure 1 shows realizations of some such point sets as chains.

convex positionp“double circle”ppdouble chainpdouble zig-zag chain Figure 1:
Some classic point sets realized as chains. For the double circle, we need to
remove one of the inner points. Chain edges are displayed black and bold,
other unavoidable hull edges in gray.

Imagine walking along the chain edges and recording at each point the
information whether we make a left turn or a right turn. It can be noted
already now that such information—while crucial—is not enough to really
capture all of the relevant combinatorial structure of a given chain. Instead,
the right way of looking at it turns out to be recording for each edge
$p_{i}p_{j}$ whether it lies above or below all the chain edges in between.

The simple linear structure inherent to chains allows us to develop a
combinatorial theory in Section 2, by which every chain admits a unique
construction starting from the primitive chain with only one edge. Two types
of sum operations, so-called convex and concave sums, are used to
“concatenate” chains, while an inversion allows to “flip” a chain on its head.
This yields for every chain a concise and unique description as an algebraic
formula. Based on this, we will also see that the number of combinatorially
different chains with $n$ chain edges is equal to $S_{n-1}$, where
$S_{k}=\sum_{i=0}^{k}\frac{1}{i+1}\binom{k}{i}\binom{k+i}{i}=\Theta(k^{-3/2}(3+\sqrt{8})^{k})$
is the $k$-th large Schröder number [2].

#### Triangulations of chains.

The unavoidable chain edges separate every triangulation cleanly into an
_upper triangulation_ of the region above the chain edges and into a _lower
triangulation_ of the region below. Therefore, both upper and lower
triangulations may be analyzed separately. It also follows that there is no
further complication due to inner vertices as one would typically encounter
them in general point sets.

There is a simple cubic time dynamic programming algorithm for counting
triangulations of simple polygons [13]. Such an algorithm can of course also
be used to count both the upper and lower triangulations of a given chain.
However, we show in Section 3 that the additional structure of chains allows
us to devise an improved quadratic time algorithm, which plays a crucial role
in the derivation of our main result.

######  Theorem 3.

Given a chain $C$ with $n$ chain edges as input, it is possible to compute the
number $\mathrm{tr}(C)$ by using only $O(n^{2})$ integer additions and
multiplications.

#### The Koch chain.

There is a particular type of chain that has caught our interest and which, to
the best of our knowledge, has not been described in the literature before. We
call it the _Koch chain_ due to its striking similarity in appearance and
definition to the famous Koch curve. More precise definitions follow later in
Definition 14; for now, suppose $K_{0}$ is a primitive chain with just one
chain edge, and let the $s$-th iteration $K_{s}$ of the Koch chain be defined
by concatenating two flipped and sufficiently flattened copies of $K_{s-1}$ in
such a way that the chain edges at the point of concatenation form a left
turn, see Figure 2.

$K_{0}$ $K_{1}$$K_{2}$$K_{3}$$K_{4}$ Figure 2:  The Koch chains $K_{s}$ for
$s=0,\dots,4$ and the corresponding Koch curves. Even though it is hard to
recognize for larger values of $s$, the changes in direction along the Koch
curve on the right are reflected one-to-one by the chain edges of the
corresponding Koch chain on the left.

Koch chains turn out to have a particularly large number of triangulations,
much more so than any other known point sets. For values of $s$ up to $21$, we
have computed the corresponding numbers of upper and lower triangulations, as
well as complete triangulations, by using our algorithm from Theorem 3. The
results are displayed in Table 1.

$s$ | $n$ | $\sqrt[n]{U}$ | $\sqrt[n]{L}$ | $\sqrt[n]{T}$ | $s$ | $n$ | $\sqrt[n]{U}$ | $\sqrt[n]{L}$ | $\sqrt[n]{T}$
---|---|---|---|---|---|---|---|---|---
0 | 1 | 1.0 | 1.0 | 1.0 | 11 | 2048 | 3.121029 | 2.858643 | 8.921910
1 | 2 | 1.0 | 1.0 | 1.0 | 12 | 4096 | 2.882177 | 3.121029 | 8.995359
2 | 4 | 1.189207 | 1.0 | 1.189207 | 13 | 8192 | 3.134955 | 2.882177 | 9.035496
3 | 8 | 1.791279 | 1.189207 | 2.130201 | 14 | 16384 | 2.889213 | 3.134955 | 9.057554
4 | 16 | 2.035453 | 1.791279 | 3.646065 | 15 | 32768 | 3.139056 | 2.889213 | 9.069406
5 | 32 | 2.558954 | 2.035453 | 5.208633 | 16 | 65536 | 2.891256 | 3.139056 | 9.075820
6 | 64 | 2.564646 | 2.558954 | 6.562814 | 17 | 131072 | 3.140236 | 2.891256 | 9.079229
7 | 128 | 2.935733 | 2.564646 | 7.529118 | 18 | 262144 | 2.891838 | 3.140236 | 9.081055
8 | 256 | 2.783587 | 2.935733 | 8.171870 | 19 | 524288 | 3.140569 | 2.891838 | 9.082019
9 | 512 | 3.075469 | 2.783587 | 8.560839 | 20 | 1048576 | 2.892001 | 3.140569 | 9.082530
10 | 1024 | 2.858643 | 3.075469 | 8.791671 | 21 | 2097152 | 3.140662 | 2.892001 | 9.082799
Table 1:  The computed numbers of triangulations of the Koch chain $K_{s}$ for
$s=0,\dots,21$, where each entry is rounded down to six decimal places. As
usual, $n$ is the number of chain edges, whereas $U$, $L$, and $T$ stand,
respectively, for the numbers of upper, lower, and complete triangulations of
the corresponding Koch chain.

In consequence, concatenating copies of $K_{21}$ side by side results in an
infinite family of point sets with at least $9.082799^{n}$ triangulations.
This alone already establishes the improved lower bound of
$\mathrm{tr}_{\mathrm{max}}(n)=\Omega(9.082799^{n})$.

#### Poly chains and Twin chains.

We were unable to nail down the exact asymptotic behavior of the number of
triangulations of $K_{s}$ as $s$ approaches infinity. It is also unclear how
much is lost due to undercounting by not considering any interactions between
the different copies of $K_{21}$ in our simple lower bound construction from
just before.

To remedy the situation somewhat, in Section 4 we define and analyze more
carefully the  _poly- $C_{0}$ chain_ (a specific way of concatenating $N$
copies of a fixed chain $C_{0}$) and the  _twin- $C_{0}$ chain_ (a
construction where two copies of a poly-$C_{0}$ chain face each other, similar
in spirit to the classic double chain). Based on these considerations, we get
a slightly improved lower bound construction, and we are also able to conclude
that the numbers in the last column of Table 1 will not grow significantly
larger than what we already have.

######  Theorem 4.

Let $C_{N}$ be the twin-$K_{21}$ chain that is made up of $2N$ copies of
$K_{21}$ for a total of $n=2N\cdot 2^{21}+1$ chain edges. Then,

$\displaystyle\lim_{N\rightarrow\infty}\sqrt[n]{\mathrm{tr}(C_{N})}=9.083095\dots,$
$\displaystyle\text{and hence
}\;\mathrm{tr}_{\mathrm{max}}(n)=\Omega(9.083095^{n}).$

######  Theorem 5.

For the Koch chain $K_{s}$ with $n=2^{s}$ chain edges, we have

$9.082799\leq\lim_{s\rightarrow\infty}\sqrt[n]{\mathrm{tr}(K_{s})}\leq
9.083139.$

##  2 Structural Properties of Chains

Recall Definition 1 from the introduction. Note that the unavoidable chain
edges form an $x$-monotone curve $p_{0}p_{1}\dots p_{n}$, to which we refer as
the _chain curve_. An edge $p_{i}p_{j}$ that is not a chain edge cannot cross
the chain curve, and so it lies either above or below that curve.

######  Definition 6.

To every chain $C$ we associate a _visibility triangle_ $V(C)$ with entries

$V(C)_{i,j}=\begin{cases}+1,&\text{if $p_{i}p_{j}$ lies above the chain
curve;}\\\ -1,&\text{if $p_{i}p_{j}$ lies below the chain curve;}\\\
\phantom{+}0,&\text{if $p_{i}p_{j}$ is a chain edge (i.e.,
$i+1=j$);}\end{cases}\qquad(0\leq i<j\leq n).$

As an example, the visibility triangles of the chains that correspond to the
classic point sets from the introduction can be seen in Figure 3. In all such
illustrations, the indices of $V(C)_{i,j}$ are understood in familiar matrix
notation; that is, $i$ indexes the row and $j$ indexes the column.

$\begin{matrix}0&+&+&+&+&+&+&+&+&+\\\ &0&+&+&+&+&+&+&+&+\\\
&&0&+&+&+&+&+&+&+\\\ &&&0&+&+&+&+&+&+\\\ &&&&0&+&+&+&+&+\\\ &&&&&0&+&+&+&+\\\
&&&&&&0&+&+&+\\\ &&&&&&&0&+&+\\\ &&&&&&&&0&+\\\ &&&&&&&&&0\\\ \end{matrix}$
convex position$\begin{matrix}0&-&+&+&+&+&+&+&+&+\\\ &0&+&+&+&+&+&+&+&+\\\
&&0&-&+&+&+&+&+&+\\\ &&&0&+&+&+&+&+&+\\\ &&&&0&-&+&+&+&+\\\ &&&&&0&+&+&+&+\\\
&&&&&&0&-&+&+\\\ &&&&&&&0&+&+\\\ &&&&&&&&0&-\\\ &&&&&&&&&0\\\ \end{matrix}$
p“double circle”p$\begin{matrix}0&-&-&-&+&+&+&+&+\\\ &0&-&-&+&+&+&+&+\\\
&&0&-&+&+&+&+&+\\\ &&&0&+&+&+&+&+\\\ &&&&0&+&+&+&+\\\ &&&&&0&-&-&-\\\
&&&&&&0&-&-\\\ &&&&&&&0&-\\\ &&&&&&&&0\\\ \end{matrix}$ pdouble
chainp$\begin{matrix}0&+&-&-&+&+&+&+&+\\\ &0&-&-&+&+&+&+&+\\\
&&0&+&+&+&+&+&+\\\ &&&0&+&+&+&+&+\\\ &&&&0&+&+&+&+\\\ &&&&&0&+&-&-\\\
&&&&&&0&-&-\\\ &&&&&&&0&+\\\ &&&&&&&&0\\\ \end{matrix}$ double zig-zag chain
Figure 3:  The visibility triangles corresponding to the chains depicted
earlier in Figure 1. For improved clarity, we only display the signs of the
respective entries.

For $i<j<k$, the triangle $p_{i}p_{j}p_{k}$ is oriented counter-clockwise if
and only if $p_{j}$ lies below the edge $p_{i}p_{k}$ or, equivalently, if and
only if $V(C)_{i,k}=+1$. It follows that two chains with the same visibility
triangle have the same order type and, therefore, the same set of crossing-
free geometric graphs and triangulations. This motivates using the visibility
triangle as the canonical representation of a chain. That is, we consider two
chains to be equal if their visibility triangles are identical; in particular,
given two chains $C_{1}$ and $C_{2}$, we write $C_{1}=C_{2}$ if
$V(C_{1})=V(C_{2})$.

The edge $p_{0}p_{n}$ plays a crucial role in determining the shape of a
chain. For example, if $V(C)_{0,n}=+1$, then this edge is the only edge on the
upper convex hull and, from a global perspective, the chain curve looks like
it is curving upwards. Conversely, if $V(C)_{0,n}=-1$, then the chain curve
looks like it is curving downwards. Correspondingly, we call a chain $C$ with
$V(C)_{0,n}\geq 0$ an _upward chain_ , and a chain with $V(C)_{0,n}\leq 0$ a
_downward chain_. This implies that every chain is either an upward or a
downward chain, and the primitive chain with only $n=1$ chain edge is the only
chain that is both.

###  2.1 Flips

Chains may be flipped upside-down by reflection at the $x$-axis, thus turning
an upward chain into a downward chain, and vice versa. See Figure 4 for an
example.

$C$$\begin{matrix}0&-&-\\\ &0&+\\\ &&0\\\ \end{matrix}$
$\overline{C}$$\begin{matrix}0&+&+\\\ &0&-\\\ &&0\\\ \end{matrix}$ Figure 4:
A chain $C$ and its flipped version $\overline{C}$ with the corresponding
visibility triangles.

######  Proposition 7.

Let $C$ be a chain with $n$ chain edges. Then, there is another chain (which
we denote by $\overline{C}$ and call the _flipped version of $C$_) with $n$
chain edges and visibility triangle

$V(\overline{C})_{i,j}=-V(C)_{i,j}\qquad(0\leq i<j\leq n).$

###  2.2 Convex and Concave Sums

Given two chains $C_{1}$ and $C_{2}$, we would like to concatenate them so
that we get a new chain containing $C_{1}$ and $C_{2}$ as substructures. As
shown in Figure 5, there are two ways to do so.

######  Proposition 8.

Let $C_{1}$ and $C_{2}$ be chains with $n_{1}$ and $n_{2}$ chain edges,
respectively. Then, there is an upward chain (which we denote by $C_{1}\vee
C_{2}$ and call the _convex sum of $C_{1}$ and $C_{2}$_) with $n_{1}+n_{2}$
chain edges and visibility triangle

$V(C_{1}\vee C_{2})_{i,j}=\begin{cases}V(C_{1})_{i,j},&\text{if
$i,j\in[0,n_{1}]$;}\\\ V(C_{2})_{i-n_{1},j-n_{1}},&\text{if
$i,j\in[n_{1},n_{1}+n_{2}]$;}\\\ +1,&\text{if
$i<n_{1}<j$;}\end{cases}\qquad(0\leq i<j\leq n_{1}+n_{2}).$

######  Proposition 9.

Similarly, there is a downward chain (which we denote by $C_{1}\wedge C_{2}$
and call the _concave sum of $C_{1}$ and $C_{2}$_) with $n_{1}+n_{2}$ chain
edges and visibility triangle

$V(C_{1}\wedge C_{2})_{i,j}=\begin{cases}V(C_{1})_{i,j},&\text{if
$i,j\in[0,n_{1}]$;}\\\ V(C_{2})_{i-n_{1},j-n_{1}},&\text{if
$i,j\in[n_{1},n_{1}+n_{2}]$;}\\\ -1,&\text{if
$i<n_{1}<j$;}\end{cases}\qquad(0\leq i<j\leq n_{1}+n_{2}).$

$C_{1}$$\begin{matrix}0&-&-\\\ &0&+\\\ &&0\\\ \end{matrix}$
$C_{2}$$\begin{matrix}0&-&+&+\\\ &0&+&+\\\ &&0&-\\\ &&&0\\\ \end{matrix}$
$C_{1}\vee
C_{2}$$\begin{matrix}{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}0}&{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}-}&{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}-}&+&+&+&+\\\
&{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}0}&{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}+}&+&+&+&+\\\
&&{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}0}&+&+&+&+\\\
&&&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}0}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}-}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}+}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}+}\\\
&&&&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}0}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}+}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}+}\\\
&&&&&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}0}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}-}\\\
&&&&&&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}0}\\\
\end{matrix}$ $C_{1}\wedge
C_{2}$$\begin{matrix}{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}0}&{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}-}&{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}-}&-&-&-&-\\\
&{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}0}&{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}+}&-&-&-&-\\\
&&{\color[rgb]{0.90625,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.90625,0.296875,0.234375}0}&-&-&-&-\\\
&&&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}0}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}-}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}+}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}+}\\\
&&&&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}0}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}+}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}+}\\\
&&&&&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}0}&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}-}\\\
&&&&&&{\color[rgb]{0.16015625,0.5,0.7265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.16015625,0.5,0.7265625}0}\\\
\end{matrix}$ Figure 5:  In the top row, two chains $C_{1}$ and $C_{2}$ with
their visibility triangles. Below, the corresponding convex and concave sums
$C_{1}\vee C_{2}$ and $C_{1}\wedge C_{2}$. Red and blue color is used to
highlight the contained substructures and their origin.

###### Proof of Proposition 8.

We focus on the convex sum; the proof for the concave sum is analogous. We
have to show that there is a point set that forms a chain with the specified
visibility triangle. Intuitively speaking, this is achieved by first
flattening the two given chains and then arranging them in a $\vee$-shape.

To be more precise, we employ vertical shearings, which are maps
$(x,y)\mapsto(x,y+\lambda x)$ in $\mathbb{R}^{2}$ for some
$\lambda\in\mathbb{R}$. Vertical shearings preserve signed areas and
$x$-coordinates. Hence, if a point set realizes a specific chain, then so does
its image under any vertical shearing.

With the help of an appropriate vertical shearing, we may realize $C_{1}$ as a
point set in the rectangle $[-1,0]\times[-1,1]$ in such a way that the first
point is at $(-1,0)$ and the last point is at $(0,0)$. Then, given any
$\varepsilon\geq 0$, we may rescale vertically to get a point set
$Q_{1}(\varepsilon)$ in the rectangle
$[-1,0]\times[-\varepsilon,\varepsilon]$. Let now $R_{1}(\varepsilon)$ be the
image of $Q_{1}(\varepsilon)$ under the vertical shearing with $\lambda=-1$.
Then, the first point of $R_{1}(\varepsilon)$ lies at $(-1,1)$, while the last
point remains at $(0,0)$. For $\varepsilon>0$, since $Q_{1}(\varepsilon)$ is a
realization of $C_{1}$, so is $R_{1}(\varepsilon)$. On the other hand, for
$\varepsilon=0$, the points of $R_{1}(\varepsilon)$ all lie on the segment
between $(-1,1)$ and $(0,0)$.

With $C_{2}$ we proceed similarly to get a point set $Q_{2}(\varepsilon)$ in
the rectangle $[0,1]\times[-\varepsilon,\varepsilon]$, but we now apply the
vertical shearing with $\lambda=1$ to get $R_{2}(\varepsilon)$ with the first
point at $(0,0)$ and the last point at $(1,1)$.

Let $T(\varepsilon)=R_{1}(\varepsilon)\cup R_{2}(\varepsilon)$. We claim that
for $\varepsilon>0$ small enough, $T(\varepsilon)$ is a chain with visibility
triangle $V(C_{1}\vee C_{2})$ as specified. Indeed, as $R_{i}(\varepsilon)$ is
a realization of $C_{i}$, we only need to check that the edges between any
point of $R_{1}(\varepsilon)$ and any point of $R_{2}(\varepsilon)$ (excluding
the common point at the origin) lie above all the points in between. Since
this is the case for $\varepsilon=0$ and $T(\varepsilon)$ depends continuously
on $\varepsilon$, the claim follows. ∎

###  2.3 Algebraic Properties

Using the formulas for the visibility triangles from the corresponding
transformations in Propositions 7, 8 and 9, it can be checked easily that the
following algebraic laws hold.

######  Lemma 10.

Let $C_{1},C_{2},C_{3}$ be arbitrary chains. Then, the following are all true.

Involution: $\displaystyle\overline{\overline{C_{1}}}$ $\displaystyle=C_{1}$
De Morgan: $\displaystyle\overline{C_{1}\vee C_{2}}$
$\displaystyle=\overline{C_{1}}\wedge\overline{C_{2}},$
$\displaystyle\overline{C_{1}\wedge C_{2}}$
$\displaystyle=\overline{C_{1}}\vee\overline{C_{2}}$ Associativity:
$\displaystyle(C_{1}\vee C_{2})\vee C_{3}$ $\displaystyle=C_{1}\vee(C_{2}\vee
C_{3}),$ $\displaystyle(C_{1}\wedge C_{2})\wedge C_{3}$
$\displaystyle=C_{1}\wedge(C_{2}\wedge C_{3})$

However, note that for example $(C_{1}\wedge C_{2})\vee C_{3}$ is not the same
chain as $C_{1}\wedge(C_{2}\vee C_{3})$.

###  2.4 Examples

We denote by $E$ the primitive chain with only $n=1$ chain edge; that is, the
visibility triangle has just the entry $V(E)_{0,1}=0$. Using this as a
building block, we may define two more fundamental chains, the _convex chain
$C_{\mathsf{cvx}}(n)$_ and the _concave chain $C_{\mathsf{ccv}}(n)$_, by
setting

$\displaystyle C_{\mathsf{cvx}}(n)$ $\displaystyle=\underbrace{E\vee\dots\vee
E}_{\text{$n$ copies}},$ $\displaystyle C_{\mathsf{ccv}}(n)$
$\displaystyle=\underbrace{E\wedge\dots\wedge E}_{\text{$n$ copies}}.$

The convex chain is an upward chain, while the concave chain is a downward
chain. Also, since $\overline{E}=E$, we get
$\overline{C_{\mathsf{cvx}}(n)}=C_{\mathsf{ccv}}(n)$ by using De Morgan’s law.
Finally, note that $C_{\mathsf{cvx}}(n)$ and $C_{\mathsf{ccv}}(n)$ are
distinct as chains, even though they both describe a set of $n+1$ points in
convex position.

As already mentioned in the introduction, many previously studied point sets
are in fact chains, or can be seen as such. Using flips as well as convex and
concave sums, we can now describe these configurations with very concise
formulas.

######  Example 11.

For any integer $k\geq 1$, the _double chain_ with $n=2k+1$ chain edges is the
chain

$C_{\mathsf{dbl}}(n)=C_{\mathsf{ccv}}(k)\vee E\vee C_{\mathsf{ccv}}(k).$

######  Example 12.

For any integer $k\geq 1$, the _zig-zag chain_ with $n=2k$ chain edges (which,
in essence, is a double circle with one of the inner points removed) is the
chain

$C_{\mathsf{zz}}(n)=\underbrace{C_{\mathsf{ccv}}(2)\vee\dots\vee
C_{\mathsf{ccv}}(2)}_{\text{$k$ copies}}.$

######  Example 13.

For any integer $k\geq 1$, the _double zig-zag chain_ with $n=4k+1$ chain
edges is the chain

$C_{\mathsf{dzz}}(n)=\overline{C_{\mathsf{zz}}(2k)}\vee
E\vee\overline{C_{\mathsf{zz}}(2k)}.$

All these examples involve formulas of constant nesting depth only. But the
tools developed up to this point allow us to also define more complicated
chains via formulas of non-constant nesting depth, without having to worry
about questions of realizability. One such chain with logarithmic nesting
depth is indeed the Koch chain.

######  Definition 14.

The _Koch chain_ $K_{s}$ is an upward chain with $n=2^{s}$ chain edges,
defined recursively via $K_{0}=E$ and
$K_{s}=\overline{K_{s-1}}\vee\overline{K_{s-1}}$ for all integers $s\geq 1$.

Indeed, after expanding the recursive definition twice and using De Morgan’s
law on both sides, we see that the formula $K_{s}=(K_{s-2}\wedge
K_{s-2})\vee(K_{s-2}\wedge K_{s-2})$ has a complete binary parse tree with
alternating convex and concave sums on any path from the root to a leaf.

###  2.5 Unique Construction

We want to prove the following result. In essence, it states that every chain
can be constructed in a unique way by using only convex and concave sums.

######  Theorem 15.

Every chain can be expressed as a formula involving convex sums, concave sums,
parentheses, and copies of the primitive chain with only one chain edge. This
formula is unique up to redundant parentheses (redundant due to associativity
as in Lemma 10).

In particular, the above theorem allows us to encode a chain with $O(n)$ bits
(as opposed to the $O(n^{2})$ bits required for the visibility triangle) and
to easily enumerate all chains of a fixed size. We further see by means of a
straightforward bijection to Schröder trees (these are ordered trees that have
no vertex of outdegree one; as such, they describe precisely the parse trees
of the unique formulas of upward chains) that the number of upward chains is
given by the little Schröder numbers [3] and the number of all chains is given
by the large Schröder numbers [2].

The theorem follows by induction from the following proposition (and from an
analogous proposition that expresses downward chains as a unique concave sum
of upward chains).

######  Proposition 16.

Let $C$ be an upward chain with $n>1$ chain edges. Suppose that the lower
convex hull of $C$ is $p_{i_{0}}p_{i_{1}}\dots p_{i_{k}}$ with
$0=i_{0}<\dots<i_{k}=n$. For $j=1,\dots,k$, let $C_{j}$ be the chain with
points $p_{i_{j-1}},\dots,p_{i_{j}}$. Then, each $C_{j}$ is a downward chain.
Moreover, $C=C_{1}\vee\dots\vee C_{k}$ and any formula that evaluates to $C$
has the same top-level structure.

###### Proof.

As $p_{i_{j-1}}p_{i_{j}}$ is an edge of the lower convex hull of $C$, it is
below all the points in between. Hence, each $C_{j}$ is indeed a downward
chain.

To prove $C=C_{1}\vee\dots\vee C_{k}$, we have to show that both chains have
the same visibility triangle. By definition of the $C_{j}$, the visibility
triangles clearly agree on all entries that stem from an edge $p_{a}p_{b}$
where $p_{a}$ and $p_{b}$ are both part of the same $C_{j}$. On the other
hand, if $p_{a}$ and $p_{b}$ are not part of the same $C_{j}$, then there is a
$j$ with $a<i_{j}<b$. As $p_{i_{j}}$ is a vertex of the lower convex hull, it
lies below the edge $p_{a}p_{b}$ and hence $V(C)_{a,b}=+1$. But this is
precisely what we also get for the visibility triangle of the convex sum
$C_{1}\vee\dots\vee C_{k}$.

For uniqueness, suppose we are given any formula for $C$. Since $C$ is assumed
to be an upward chain and since any concave sum is a downward chain, the
formula must be of the form $C^{\prime}_{1}\vee\dots\vee
C^{\prime}_{k^{\prime}}$. We may further assume that each $C^{\prime}_{j}$ is
a downward chain by omitting redundant parentheses. Observe now that in any
such convex sum of downward chains, the resulting lower convex hull is
determined by the points that are shared by any two consecutive chains
$C^{\prime}_{j}$. Since the given formula evaluates to $C$, we must have
$k^{\prime}=k$ and $C^{\prime}_{j}=C_{j}$ for all $j$. ∎

###  2.6 Geometric Characterization

As already mentioned in the introduction, the chain edges together with the
hull edge $p_{0}p_{n}$ form a spanning cycle of unavoidable edges. We are now
ready to prove that this property characterizes chains geometrically in terms
of order types.

Suppose we are given a set of $n+1$ points $p_{0},p_{1},\dots,p_{n}$ as in
Theorem 2. Without loss of generality, let $\mathrm{SC}=p_{0}p_{1}\dots p_{n}$
be the spanning cycle of unavoidable edges in counter-clockwise order, with
$p_{0}p_{n}$ an edge of the convex hull, which we call the _base edge_. As
$\mathrm{SC}$ consists of unavoidable edges only, it cannot be crossed by any
edge that is not part of $\mathrm{SC}$. Hence, we can associate a visibility
triangle with the given point set, similar to the visibility triangle of a
chain, by setting

$V_{i,j}=\begin{cases}+1,&\text{if $p_{i}p_{j}$ is inside $\mathrm{SC}$ or the
base edge;}\\\ -1,&\text{if $p_{i}p_{j}$ is outside $\mathrm{SC}$;}\\\
\phantom{+}0,&\text{if $p_{i}p_{j}$ is part of $\mathrm{SC}$ (i.e.,
$i+1=j$);}\end{cases}\qquad(0\leq i<j\leq n).$

######  Proposition 17.

For $i<j<k$, the triangle $p_{i}p_{j}p_{k}$ is oriented counter-clockwise if
and only if we have $V_{i,k}=+1$.

###### Proof.

We will make use of the following key fact about simple polygons. Consider two
simple polygons that share an edge $e$, but do not touch or intersect in any
other way. Then, exactly one of the following is true. Either one polygon is
contained in the other, or the two polygons touch the edge $e$ from different
sides.

We split the proof of the proposition into the following three cases.

  * •

Suppose that $p_{i}p_{k}$ is the base edge (i.e., $i=0$ and $k=n$). Then, the
triangle $p_{i}p_{j}p_{k}$ is always oriented counter-clockwise since
$p_{i}p_{k}=p_{0}p_{n}$ is an edge of the convex hull. Also, we have
$V_{i,k}=V_{0,n}=+1$ by definition.

  * •

Suppose that $p_{i}p_{k}$ is not the base edge (i.e., $i\neq 0$ or $k\neq n$)
and inside $\mathrm{SC}$ (i.e., $V_{i,k}=+1$). Let $\mathrm{SC}^{\prime}$
denote the simple polygon $p_{0},p_{1},\dots,p_{i},p_{k},p_{k+1},\dots,p_{n}$.
Let us now apply our key fact about simple polygons to $\mathrm{SC}^{\prime}$
and the triangle $p_{i}p_{j}p_{k}$. These two polygons share the edge
$p_{i}p_{k}$, but do not touch or intersect in any other way since all other
edges of $\mathrm{SC}^{\prime}$ are unavoidable. Moreover, since $p_{j}$ is
outside of $\mathrm{SC}^{\prime}$, the triangle is not contained in
$\mathrm{SC}^{\prime}$. On the other hand, $\mathrm{SC}^{\prime}$ contains the
hull vertices $p_{0}$ and $p_{n}$, and so $\mathrm{SC}^{\prime}$ is also not
contained in the triangle. Therefore, since $\mathrm{SC}^{\prime}$ touches the
edge $p_{i}p_{k}$ from the left side, $p_{j}$ has to be to the right of
$p_{i}p_{k}$, and so the triangle $p_{i}p_{j}p_{k}$ is indeed oriented
counter-clockwise.

  * •

Suppose that $p_{i}p_{k}$ is not the base edge (i.e., $i\neq 0$ or $k\neq n$)
and outside $\mathrm{SC}$ (i.e., $V_{i,k}=-1$). Let again
$\mathrm{SC}^{\prime}$ denote the simple polygon
$p_{0},p_{1},\dots,p_{i},p_{k},p_{k+1},\dots,p_{n}$, and let us again apply
our key fact to $\mathrm{SC}^{\prime}$ and $p_{i}p_{j}p_{k}$. In this case,
since $p_{j}$ lies inside of $\mathrm{SC}^{\prime}$, the triangle is contained
in $\mathrm{SC}^{\prime}$. Therefore, since $\mathrm{SC}^{\prime}$ touches the
edge $p_{i}p_{k}$ from the left side, $p_{j}$ has to be to the left of
$p_{i}p_{k}$, and so the triangle $p_{i}p_{j}p_{k}$ is indeed oriented
clockwise. ∎

Having Proposition 17 at hand, it will now suffice to construct a chain whose
visibility triangle agrees with $V$ in order to finish the proof of Theorem 2.

Let thus $p_{i_{0}},p_{i_{1}},\dots,p_{i_{k}}$ be the vertices of the convex
hull with $0=i_{0}<\dots<i_{k}=n$. For $1\leq j\leq k$, let
$P_{j}=\\{p_{i_{j-1}},\dots,p_{i_{j}}\\}$. We now see that either $P_{j}$
consists of only two points or that it admits a spanning cycle of unavoidable
edges, namely $\mathrm{SC}_{j}=p_{i_{j-1}}p_{i_{j-1}+1}\dots p_{i_{j}}$ with
base edge $p_{i_{j-1}}p_{i_{j}}$. The situation is depicted in Figure 6.

$p_{0}$$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p_{5}$$p_{6}$$p_{7}$$p_{8}$$p_{9}$$p_{10}$$p_{11}$$p_{12}$$\mathrm{SC}$$\mathrm{SC}_{2}$$\mathrm{SC}_{4}$$\mathrm{SC}_{6}$
Figure 6:  The situation in the proof of Theorem 2. Beware that this is just a
sketch; in reality, the pockets would need to be much more narrow in order to
make all edges of $\mathrm{SC}$ unavoidable.

Note that the inside of $\mathrm{SC}_{j}$ is outside of $\mathrm{SC}$. In
fact, $\mathrm{SC}_{j}$ forms a so-called pocket of $\mathrm{SC}$, which means
that all edges of the cycle $\mathrm{SC}_{j}$ except for
$p_{i_{j-1}}p_{i_{j}}$ are also edges of $\mathrm{SC}$.

Using the statement of Theorem 2 inductively for the strictly smaller set of
points $P_{j}$, we now see that there is a chain $C_{j}$ with the same order
type as $P_{j}$, that is, with

$V(C_{j})_{a,b}=\begin{cases}+1,&\text{if $p_{i_{j-1}+a}p_{i_{j-1}+b}$ is
inside $\mathrm{SC}_{j}$ or the base edge;}\\\ -1,&\text{if
$p_{i_{j-1}+a}p_{i_{j-1}+b}$ is outside $\mathrm{SC}_{j}$;}\\\
\phantom{+}0,&\text{if $p_{i_{j-1}+a}p_{i_{j-1}+b}$ is part of
$\mathrm{SC}_{j}$ (i.e., $a+1=b$);}\end{cases}\qquad(0\leq a<b\leq
i_{j}-i_{j-1}).$

Let us consider the flipped version $\overline{C_{j}}$. As noted before, the
inside of $\mathrm{SC}_{j}$ is outside of $\mathrm{SC}$. As $\mathrm{SC}_{j}$
moreover forms a pocket of $\mathrm{SC}$, any edge outside of
$\mathrm{SC}_{j}$ is inside $\mathrm{SC}$. Hence,

$V(\overline{C_{j}})_{a,b}=\begin{cases}+1,&\text{if
$p_{i_{j-1}+a}p_{i_{j-1}+b}$ is inside $\mathrm{SC}$;}\\\ -1,&\text{if
$p_{i_{j-1}+a}p_{i_{j-1}+b}$ is outside $\mathrm{SC}$;}\\\
\phantom{+}0,&\text{if $p_{i_{j-1}+a}p_{i_{j-1}+b}$ is part of $\mathrm{SC}$
(i.e., $a+1=b$);}\end{cases}\qquad(0\leq a<b\leq i_{j}-i_{j-1}).$

We claim that $C=\overline{C_{1}}\vee\dots\vee\overline{C_{k}}$ has the
desired visibility triangle $V$. We have just seen that the entries stemming
from the individual $\overline{C_{j}}$ are correct. So, all that is left to
observe is that edges between different pockets lie inside of $\mathrm{SC}$,
which is indeed the case.

###  2.7 Point Sets that are Almost Chains

Recall the assumption in Theorem 2 which says that at least one of the edges
of the unavoidable spanning cycle must be a convex hull edge. This assumption
is crucial since, for example, the classic double circle cannot be realized as
a chain even though it admits an unavoidable spanning cycle. Nevertheless, we
can show that the corresponding order types are reasonably close to being a
chain, in the sense that a single point may be replaced by two new points in
order to obtain a chain. In addition, this transformation does not change the
number of triangulations by much.

######  Theorem 18.

Let $P$ be a set of $n$ points that admits an unavoidable spanning cycle
$p_{1},\dots,p_{n}$ where $p_{n}$ is a vertex of the convex hull. Then, there
exists a chain $C=q_{0},q_{1},\dots,q_{n}$ such that $p_{1},\dots,p_{n-1}$ has
the same order type as $q_{1},\dots,q_{n-1}$. Moreover, we have

$2\cdot\mathrm{tr}(P)\leq\mathrm{tr}(C)\leq(n-1)\cdot\mathrm{tr}(P).$

###### Proof.

We mimic the proof of Theorem 2 from the previous subsection. That is,
consider the augmented sequence $p_{0},p_{1},\dots,p_{n}$ with $p_{0}=p_{n}$
and let $p_{i_{0}},\dots,p_{i_{k}}$ be the vertices of the convex hull with
$0=i_{0}<\dots<i_{k}=n$ and $k\geq 3$. For $1\leq j\leq k$, let
$P_{j}=\\{p_{i_{j-1}},\dots,p_{i_{j}}\\}$. Each such $P_{j}$ again forms a so-
called pocket, which may be realized as a chain $C_{j}$. The construction is
concluded by defining $C=C_{1}\vee\dots\vee C_{k}$. Observe by using a
statement analogous to Proposition 17 that all involved triangles maintain
their orientation, except that the duplicated points $q_{0}$ and $q_{n}$ that
came from $p_{0}=p_{n}$ behave antagonistically with respect to points in
$C_{k}$ and $C_{1}$, respectively. For example, the triangle $q_{i}q_{j}q_{n}$
for $q_{i},q_{j}\in C_{1}$ with $i<j$ is always oriented counter-clockwise,
even if originally $p_{i}p_{j}p_{n}$ was oriented clockwise.

Let us fix any triangulation of $P$. We show how to map it injectively to two
distinct triangulations of $C$, thus proving the first inequality. First of
all, note that the triangulations of the individual pockets of $P$ directly
correspond to a lower triangulation of $C$, which means that we may limit our
attention to the upper triangulation of $C$. There, we start by either adding
the triangle $q_{0}q_{1}q_{n}$ or the triangle $q_{0}q_{n-1}q_{n}$. In the
first case, we are left to triangulate the simple polygon $q_{1},\dots,q_{n}$,
whereas in the second case, the respective polygon is $q_{0},\dots,q_{n-1}$.
In the first case, any remaining edge $p_{i}p_{j}$ of the fixed triangulation
of $P$ (i.e., any edge that is not contained inside of a pocket) is simply
mapped to the edge $q_{i}q_{j}$ in $C$. In the second case, we do the same
except that the point $q_{0}$ takes the role of $q_{n}$.

Let us fix any triangulation of $C$. To prove the second inequality, we
construct a corresponding triangulation of $P$ in such a way that at most
$n-1$ triangulations of $C$ have the same correspondence. First of all, we may
again map the lower triangulation of $C$ to triangulations of the individual
pockets of $P$. As far as the upper triangulation of $C$ is concerned, there
is exactly one triangle of the form $q_{0}q_{m}q_{n}$ where $1\leq m\leq n-1$.
This triangle is mapped to the edge $p_{n}p_{m}$ in the corresponding
triangulation of $P$. This has the effect of splitting the inside of the
unavoidable spanning cycle of $P$ into two separate simple polygons that are
left to be triangulated. They are triangulated simply by mapping all the
remaining edges $q_{i}q_{j}$ of the upper triangulation of $C$ to edges
$p_{i}p_{j}$, where any appearance of $q_{0}$ is mapped to $p_{n}$. ∎

##  3 Triangulations of Chains

In the previous section, we have seen that any chain can be expressed as a
formula involving only convex and concave sums. Our goal here is to understand
how triangulations behave with respect to such convex and concave sums. In
order for this to work out, we have to consider not just triangulations, but a
more general notion of partial triangulations.

We start by decomposing triangulations of a chain $C$ into an upper and a
lower part. An edge $p_{i}p_{j}$ is an _upper edge_ if $V(C)_{i,j}=+1$, a
_chain edge_ if $V(C)_{i,j}=0$, and a _lower edge_ if $V(C)_{i,j}=-1$. That
is, upper edges lie above the chain curve, while lower edges lie below.

######  Definition 19.

An _upper (lower) triangulation_ of a given chain $C$ is a crossing-free
geometric graph on $C$ that is edge-maximal subject to only containing chain
edges and upper (lower) edges. We denote the number of upper and lower
triangulations by $U(C)$ and $L(C)$, respectively, and as always the number of
(complete) triangulations by $\operatorname{tr}(C)$.

Note that the chain edges are contained in every upper and lower
triangulation. Moreover, every triangulation is the union of a unique upper
and a unique lower triangulation, which implies
$\operatorname{tr}(C)=U(C)\cdot L(C)$. A lower triangulation of a chain $C$ is
an upper triangulation of the flipped version $\overline{C}$, and therefore
$L(C)=U(\overline{C})$. For this reason, we may restrict our attention to
studying only upper triangulations.

Intuitively speaking, we can create a partial upper triangulation by combining
all the chain edges with some upper edges, in such a way that all bounded
faces are triangles. Note that then, only some of the used edges are visible
from above.

######  Definition 20.

Let $C$ be any chain with $n$ chain edges, and let $V=p_{i_{0}}p_{i_{1}}\dots
p_{i_{v}}$ with $0=i_{0}<i_{1}<\dots<i_{v}=n$ be an (x-monotone) curve
composed of chain edges and upper edges only. A _partial upper triangulation
of $C$ (with visible edges $V$)_ consists of all chain edges, all edges in
$V$, and a triangulation of the areas between the two.

Figure 7 depicts some partial upper triangulations and their visible edges. We
are interested in counting such triangulations parameterized by the number of
triangles. It can be noted that a partial upper triangulation with $k$
triangles has $n-k$ visible edges.

Figure 7:  Four partial upper triangulations of the “double circle” with ten,
six, three, and one visible edge, respectively. As usual, chain edges are in
bold, while visible edges are in blue.

######  Definition 21.

Let $C$ be any chain with $n$ chain edges. For $k=0,\dots,n-1$, let $t_{k}(C)$
be the number of partial upper triangulations of $C$ with $k$ triangles (i.e.,
with $n-k$ visible edges). The _upper triangulation polynomial of $C$_ is the
corresponding generating function

$T_{C}(x)=\sum_{k=0}^{n-1}t_{k}(C)x^{k}.$

As an example, enumerating all partial upper triangulations of the convex
chain $C_{\mathsf{cvx}}(4)$ shows that
$T_{C_{\mathsf{cvx}}(4)}(x)=1+3x+5x^{2}+5x^{3}$. In general, note that for
every chain $C$ we have $t_{0}(C)=1$ and that the leading coefficient of
$T_{C}(x)$ is equal to $U(C)$. Moreover, we may again think of
$T_{\overline{C}}(x)$ as the “lower triangulation polynomial” of $C$.

###  3.1 Convex and Concave Sums

Let us start with the easy case. For concave sums, we can establish the
following relation.

######  Lemma 22.

A partial upper triangulation of $C_{1}\wedge C_{2}$ is the union of a unique
partial upper triangulation of $C_{1}$ and a unique partial upper
triangulation of $C_{2}$. Hence,

$\displaystyle T_{C_{1}\wedge C_{2}}(x)=T_{C_{1}}(x)\cdot T_{C_{2}}(x),$
$\displaystyle U(C_{1}\wedge C_{2})=U(C_{1})\cdot U(C_{2}).$

Convex sums are more tricky. The main insight is that every partial upper
triangulation of $C_{1}\vee C_{2}$ consists of a partial upper triangulation
of $C_{1}$, a partial upper triangulation of $C_{2}$, and some edges between
$C_{1}$ and $C_{2}$. More precisely:

######  Proposition 23.

There is a triangle-preserving bijection between

  * •

all triples $(T_{1},T_{2},T_{3})$ where $T_{1}$ is a partial upper
triangulation of $C_{1}$ (with $v_{1}$ visible edges), $T_{2}$ is a partial
upper triangulation of $C_{2}$ (with $v_{2}$ visible edges), and $T_{3}$ is a
partial upper triangulation of the convex sum $C_{\mathsf{ccv}}(v_{1})\vee
C_{\mathsf{ccv}}(v_{2})$, and

  * •

all partial upper triangulations of $C_{1}\vee C_{2}$.

$C_{1}$$C_{2}$$C_{\mathsf{ccv}}(2)\vee C_{\mathsf{ccv}}(3)$$C_{1}\vee C_{2}$
Figure 8:  From left to right, the respective partial upper triangulations
$T_{1}$ of $C_{1}$, $T_{2}$ of $C_{2}$, $T_{3}$ of $C_{\mathsf{ccv}}(2)\vee
C_{\mathsf{ccv}}(3)$, and the resulting partial upper triangulation of
$C_{1}\vee C_{2}$ as in Proposition 23.

This bijection is defined by taking the union of all triangles, see Figure 8.
The proposition then directly implies the following equation for the upper
triangulation polynomial.

######  Lemma 24.

Let $C_{1}$ and $C_{2}$ be chains with $n_{1}$ and $n_{2}$ chain edges,
respectively. Then,

$T_{C_{1}\vee
C_{2}}(x)=\sum_{k_{1}=0}^{n_{1}-1}\sum_{k_{2}=0}^{n_{2}-1}t_{k_{1}}(C_{1})\cdot
t_{k_{2}}(C_{2})\cdot x^{k_{1}+k_{2}}\cdot
T_{C_{\mathsf{ccv}}(n_{1}-k_{1})\,\vee\,C_{\mathsf{ccv}}(n_{2}-k_{2})}(x).$

Let us consider the special case of a convex sum of two concave chains with
$n_{1}$ and $n_{2}$ chain edges, respectively. Note that any partial upper
triangulation of such a chain has at most one upper edge that is visible.
Summing over all possibilities for that edge and using the formula from the
analysis of the classic double chain from [17], we get

$\displaystyle
T_{C_{\mathsf{ccv}}(n_{1})\,\vee\,C_{\mathsf{ccv}}(n_{2})}(x)=1+\sum_{l=1}^{n_{1}}\sum_{r=1}^{n_{2}}\binom{l+r-2}{l-1}x^{l+r-1}.$

Combining the above equation with Lemma 24 allows us to compute $T_{C_{1}\vee
C_{2}}(x)$ from $T_{C_{1}}(x)$ and $T_{C_{2}}(x)$. Furthermore, by comparing
the coefficients in the formulas from Lemmas 22 and 24, we get the following
obvious but important fact.

######  Corollary 25.

$C_{1}\vee C_{2}$ has at least as many (partial) upper triangulations as
$C_{1}\wedge C_{2}$. That is,

$\displaystyle\forall k\colon t_{k}(C_{1}\vee C_{2})\geq t_{k}(C_{1}\wedge
C_{2}),$ $\displaystyle U(C_{1}\vee C_{2})\geq U(C_{1}\wedge C_{2}).$

Finally, note that the two chains $C_{1}\vee C_{2}$ and $C_{2}\vee C_{1}$ can
be quite different from a geometric point of view. But in terms of the number
of triangulations, they are the same.

######  Corollary 26.

For any two chains $C_{1}$ and $C_{2}$, we have

$\displaystyle T_{C_{1}\vee C_{2}}(x)=T_{C_{2}\vee C_{1}}(x),$ $\displaystyle
T_{C_{1}\wedge C_{2}}(x)=T_{C_{2}\wedge C_{1}}(x).$

###  3.2 Dynamic Programming

In this subsection, we show how to use dynamic programming in order to speed
up the computations for a convex sum. To simplify the analysis, we assume a
computational model where all additions and multiplications take only constant
time.

######  Proposition 27.

Let $C_{1}$ and $C_{2}$ be chains with $n_{1}$ and $n_{2}$ chain edges,
respectively. Given the coefficients of $T_{C_{1}}(x)$ and $T_{C_{2}}(x)$, we
can compute $T_{C_{1}\vee C_{2}}(x)$ in $O(n_{1}n_{2})$ time.

Recall that by Theorem 15, we can write any chain $C$ as a formula involving
only convex sums, concave sums, and primitive chains with only one chain edge.
Therefore, using Proposition 27 for convex sums and Lemma 22 for concave sums,
we are able to compute $T_{C}(x)$ in quadratic time. Clearly, this proves
Theorem 3 from the introduction.

###### Proof of Proposition 27.

Observe that every partial upper triangulation of $C_{1}\vee C_{2}$ either
corresponds to a partial upper triangulation of $C_{1}\wedge C_{2}$, or it has
a unique visible upper edge that connects a vertex of $C_{1}$ with a vertex of
$C_{2}$. Let us call this edge the _bridge_. Let further $\mathrm{DP}[l][r]$
be the number of partial upper triangulations whose visible edges consist of
$l$ visible edges in $C_{1}$, followed by the bridge, followed by $r$ visible
edges in $C_{2}$. Then,

$T_{C_{1}\vee C_{2}}(x)=T_{C_{1}\wedge
C_{2}}(x)+\sum_{l=0}^{n_{1}-1}\sum_{r=0}^{n_{2}-1}\mathrm{DP}[l][r]\cdot
x^{n_{1}+n_{2}-l-r-1}.$

To compute the table $\mathrm{DP}$, let us see what happens when we remove the
bridge. We either end up with a partial upper triangulation of $C_{1}\wedge
C_{2}$ with $l+1$ and $r+1$ visible edges in $C_{1}$ and $C_{2}$,
respectively, or we get a new bridge, which used to be an edge of the triangle
below the old bridge. In the latter case, depending on which of the two
possible edges this is, we end up with one more visible edge in either $C_{1}$
or $C_{2}$. Figure 9 depicts these three cases. To summarize, for all $l$ and
$r$ ($0\leq l<n_{1},0\leq r<n_{2}$),

$\mathrm{DP}[l][r]=t_{n_{1}-l-1}(C_{1})\cdot
t_{n_{2}-r-1}(C_{2})+\mathrm{DP}[l+1][r]+\mathrm{DP}[l][r+1],$

with the base case $\mathrm{DP}[n_{1}][r]=\mathrm{DP}[l][n_{2}]=0$. Therefore,
filling up the table $\mathrm{DP}$ takes $O(n_{1}n_{2})$ time, as desired. ∎

$C_{1}$$C_{2}$$C_{1}$$C_{2}$$C_{1}$$C_{2}$ Figure 9:  The three cases when
removing the bridge from a partial upper triangulation of $C_{1}\vee C_{2}$ in
the proof of Proposition 27. On the left, both $C_{1}$ and $C_{2}$ gain a
visible edge. In the middle, only $C_{1}$ gains a visible edge. On the right,
only $C_{2}$ gains a visible edge. The current bridge is red, and the edge
that becomes the new bridge is blue.

###  3.3 Koch Chains

Recall Definition 14 and that the formula for Koch chains expands to the
nested expression

$K_{s}=(K_{s-2}\wedge K_{s-2})\vee(K_{s-2}\wedge K_{s-2})$

with alternating convex and concave sums. This repeated mixing of the two
types of sums appears to make an exact analysis of the number of
triangulations of $K_{s}$ very difficult.

Instead, we have implemented the quadratic time algorithm from the previous
subsection and used it to compute $T_{K_{s}}(x)$ and $T_{\overline{K_{s}}}(x)$
for all $s\leq 21$. To deal with the exponentially growing coefficients, we
rely on a custom floating point type with a $64$ bit mantissa and a $32$ bit
exponent from the boost multiprecision library. As only additions and
multiplications are involved, we do not have to deal with numerical issues; in
fact, the rounding errors grow at most linearly. In addition, we make use of
multi-threading and take advantage of symmetries of $K_{s}$ for a constant
factor speed-up. This allows us to compute $T_{K_{21}}(x)$ in around a day on
a regular workstation (Intel i7-6700HQ, 2.6GHz).

Table 1 from the introduction lists the resulting numbers. For example,
$K_{21}$ has approximately $9.082799^{n}$ triangulations, where $n=2^{21}$. In
the next section, we show how the computed coefficients of $T_{K_{21}}(x)$ can
be used to give bounds on $\operatorname{tr}(K_{s})$ as $s\to\infty$.

##  4 Poly Chains and Twin Chains

Let $C_{0}$ be a fixed chain with $m$ chain edges. We want to define two
particular families of chains that can be built from many copies of $C_{0}$
via concave and convex sums.

######  Definition 28.

For integers $N\geq 1$, the _poly- $C_{0}$ chains (of length $n=Nm$)_ are the
chains

$C_{\mathsf{poly}}(C_{0},N)=\underbrace{\overline{C_{0}}\vee\dots\vee\overline{C_{0}}}_{\text{$N$
copies}}.$

######  Definition 29.

For integers $N\geq 1$, the _twin- $C_{0}$ chains (of length $n=2Nm+1$)_ are
the chains

$C_{\mathsf{twin}}(C_{0},N)=\overline{C_{\mathsf{poly}}(C_{0},N)}\vee
E\vee\overline{C_{\mathsf{poly}}(C_{0},N)}.$

Note that both resulting chains are upward chains, as long as $N>1$. For
example, the poly-$E$ chains are the convex chains, the twin-$E$ chains are
the classic double chains, and the twin-$(E\vee E)$ chains are the double zig-
zag chains.

We are interested in the asymptotic behavior of the number of triangulations
of these constructions as $N$ goes to infinity. Lemma 22 allows us to express
the number of lower triangulations in terms of upper triangulations.

$\displaystyle L(C_{\mathsf{poly}}(C_{0},N))$
$\displaystyle=U(C_{0}\wedge\dots\wedge C_{0})=U(C_{0})^{N}$ $\displaystyle
L(C_{\mathsf{twin}}(C_{0},N))$
$\displaystyle=U(C_{\mathsf{poly}}(C_{0},N)\wedge E\wedge
C_{\mathsf{poly}}(C_{0},N))=U(C_{\mathsf{poly}}(C_{0},N))^{2}$

For the upper triangulations, we make use of the following general result,
whose proof can be found in the following subsections.

######  Theorem 30.

The poly-$C_{0}$ chains of length $n$ have $\widetilde{\Theta}(\lambda^{n})$
upper triangulations (where the $\widetilde{\Theta}$-notation suppresses
potential additional factors that are polynomial in $n$), while the
twin-$C_{0}$ chains of length $n$ have $\widetilde{\Theta}(\tau^{n})$ upper
triangulations, where

$\displaystyle\lambda=\sqrt[m]{\sum_{k=1}^{m}2^{k}(k+1)\cdot
t_{m-k}(\overline{C_{0}})},$
$\displaystyle\tau=\sqrt[m]{\sum_{k=1}^{m}2^{k}\cdot t_{m-k}(C_{0})}.$

It follows that the twin-$C_{0}$ chains of length $n$ have
$\widetilde{\Theta}((\lambda\tau)^{n})$ complete triangulations.

######  Example 31.

Let us analyze the poly-$C_{\mathsf{cvx}}(4)$ chains and
twin-$C_{\mathsf{cvx}}(4)$ chains. We have

$\displaystyle T_{\overline{C_{\mathsf{cvx}}(4)}}(x)=1,$ $\displaystyle
T_{C_{\mathsf{cvx}}(4)}(x)=1+3x+5x^{2}+5x^{3},$

which yields $\lambda=\sqrt[4]{80}$ and $\tau=\sqrt[4]{70}$. Therefore, the
twin-$C_{\mathsf{cvx}}(4)$ chains have
$\widetilde{\Theta}(\sqrt[4]{5600}^{n})$ triangulations, where
$\sqrt[4]{5600}\approx 8.6506154$. Note that these chains are the generalized
double zig-zag chains from [12]. By comparison, the numerical bound there was
$\Omega(8.6504^{n})$.

In the same way, by using the many coefficients of $T_{K_{s}}(x)$ and
$T_{\overline{K_{s}}}(x)$ that we found for all $s\leq 21$ with our algorithm
from the previous section, we can also compute the corresponding values of
$\lambda$ and $\tau$ for poly-Koch chains and twin-Koch chains. The results
can be found in Table 2. The last row in particular allows us to analyze
twin-$K_{21}$ chains and, therefore, prove Theorem 4 from the introduction.

$s$ | $m$ | $\lambda$ | $\tau$ | $\lambda\tau$ | $s$ | $m$ | $\lambda$ | $\tau$ | $\lambda\tau$
---|---|---|---|---|---|---|---|---|---
0 | 1 | 4.0 | 2.0 | 8.0 | 11 | 2048 | 2.894607 | 3.137597 | 9.082113
1 | 2 | 3.464101 | 2.449489 | 8.485281 | 12 | 4096 | 3.142184 | 2.890518 | 9.082542
2 | 4 | 3.534118 | 2.449489 | 8.656787 | 13 | 8192 | 2.892806 | 3.139805 | 9.082850
3 | 8 | 3.124013 | 2.841004 | 8.875335 | 14 | 16384 | 3.141127 | 2.891623 | 9.082957
4 | 16 | 3.290140 | 2.721989 | 8.955727 | 15 | 32768 | 2.892276 | 3.140445 | 9.083034
5 | 32 | 2.974654 | 3.033787 | 9.024469 | 16 | 65536 | 3.140819 | 2.891940 | 9.083061
6 | 64 | 3.191872 | 2.835019 | 9.049019 | 17 | 131072 | 2.892123 | 3.140627 | 9.083081
7 | 128 | 2.919234 | 3.106209 | 9.067752 | 18 | 262144 | 3.140731 | 2.892029 | 9.083087
8 | 256 | 3.157095 | 2.874272 | 9.074351 | 19 | 524288 | 2.892080 | 3.140677 | 9.083092
9 | 512 | 2.900536 | 3.130176 | 9.079191 | 20 | 1048576 | 3.140706 | 2.892054 | 9.083094
10 | 1024 | 3.145716 | 2.886746 | 9.080887 | 21 | 2097152 | 2.892068 | 3.140692 | 9.083095
Table 2:  The computed values of $\lambda$ and $\tau$ as in Theorem 30 for the
special case $C_{0}=K_{s}$, where each entry is rounded down to six decimal
places.

######  Corollary 32.

The twin-$K_{21}$ chains of length $n$ have $\widetilde{\Theta}(\tau^{n})$
upper triangulations, $\widetilde{\Theta}(\lambda^{n})$ lower triangulations,
and hence $\widetilde{\Theta}((\lambda\tau)^{n})$ complete triangulations,
where $\tau\approx 3.140692$, $\lambda\approx 2.892068$, and
$\lambda\tau\approx 9.083095$.

The next two lemmas, when combined with the first part of Theorem 30, can
further be used to prove asymptotic bounds for families of chains that are
built from the same $C_{0}$.

######  Lemma 33.

Let $C$ be any chain that can be written as a formula involving convex sums,
concave sums and exactly $N$ copies of $C_{0}$. Then,

$U(C_{0})^{N}\leq U(C)\leq U(C_{\mathsf{poly}}(\overline{C_{0}},N)).$

###### Proof.

We get $U(C_{0}\wedge\dots\wedge C_{0})\leq U(C)\leq U(C_{0}\vee\dots\vee
C_{0})$ by using induction on $N$ combined with Corollary 25. Lemma 22 and the
definition of poly-$\overline{C_{0}}$ chains then concludes the proof. ∎

######  Lemma 34.

In the same setting, we have

$\operatorname{tr}(C_{0})^{N}\leq\operatorname{tr}(C)\leq
U(C_{\mathsf{poly}}(C_{0},N))\cdot U(C_{\mathsf{poly}}(\overline{C_{0}},N)).$

###### Proof.

Apply Lemma 33 twice. First to $C$ with $C_{0}$, then to $\overline{C}$ with
$\overline{C_{0}}$. ∎

The Koch chains $K_{s}$ with $s\geq 21$ can be written as formulas involving
only copies of $K_{21}$ (or only copies of $\overline{K_{21}}$, depending on
the parity of $s$), and so Lemma 34 applies to them. For the lower bound, we
obtain $9.082799^{n}\leq\operatorname{tr}(K_{s})$ for all $s\geq 21$ from the
last entry in Table 1. For the upper bound, we make use of Table 3, which
contains once more the computed values $\lambda$ for poly-$K_{s}$ chains, but
it also includes the corresponding values (denoted by $\overline{\lambda}$)
for poly-$\overline{K_{s}}$ chains. Note that poly-$\overline{K_{s}}$ chains
are in fact nothing else than poly-$K_{s-1}$ chains, and so the values
$\lambda$ and $\overline{\lambda}$ are simply shifted by one index. For all
$s\geq 21$, we obtain $\operatorname{tr}(K_{s})\leq
U(C_{\mathsf{poly}}(K_{21},N))\cdot
U(C_{\mathsf{poly}}(\overline{K_{21}},N))=\widetilde{\Theta}((\lambda\overline{\lambda})^{n})$
where $\lambda\overline{\lambda}\approx 9.083138$. Clearly, this proves
Theorem 5 from the introduction.

$s$ | $m$ | $\lambda$ | $\overline{\lambda}$ | $\lambda\overline{\lambda}$ | $s$ | $m$ | $\lambda$ | $\overline{\lambda}$ | $\lambda\overline{\lambda}$
---|---|---|---|---|---|---|---|---|---
0 | 1 | 4.0 | 4.0 | 16.0 | 11 | 2048 | 2.894607 | 3.145716 | 9.105615
1 | 2 | 3.464101 | 4.0 | 13.856406 | 12 | 4096 | 3.142184 | 2.894607 | 9.095390
2 | 4 | 3.534118 | 3.464101 | 12.242546 | 13 | 8192 | 2.892806 | 3.142184 | 9.089731
3 | 8 | 3.124013 | 3.534118 | 11.040634 | 14 | 16384 | 3.141127 | 2.892806 | 9.086674
4 | 16 | 3.290140 | 3.124013 | 10.278444 | 15 | 32768 | 2.892276 | 3.141127 | 9.085007
5 | 32 | 2.974654 | 3.290140 | 9.787032 | 16 | 65536 | 3.140819 | 2.892276 | 9.084117
6 | 64 | 3.191872 | 2.974654 | 9.494717 | 17 | 131072 | 2.892123 | 3.140819 | 9.083637
7 | 128 | 2.919234 | 3.191872 | 9.317823 | 18 | 262144 | 3.140731 | 2.892123 | 9.083383
8 | 256 | 3.157095 | 2.919234 | 9.216301 | 19 | 524288 | 2.892080 | 3.140731 | 9.083247
9 | 512 | 2.900536 | 3.157095 | 9.157271 | 20 | 1048576 | 3.140706 | 2.892080 | 9.083176
10 | 1024 | 3.145716 | 2.900536 | 9.124266 | 21 | 2097152 | 2.892068 | 3.140706 | 9.083138
Table 3:  The computed values of $\lambda$ for poly-$K_{s}$ chains, the
corresponding $\overline{\lambda}$ for poly-$\overline{K_{s}}$ chains, and the
product $\lambda\overline{\lambda}$ for the resulting upper bound given by
Lemma 34, where each entry is rounded down to six decimal places.

###  4.1 Tools for the proof of Theorem 30

We use similar ideas as in the analysis of the generalized double zig-zag
chain by Dumitrescu et al. (Section 2 of [12]), with three key improvements
that allow us to get an exact $\widetilde{\Theta}$ instead of just a numerical
lower bound.

#### First improvement.

Our first improvement is that our chain framework allows us to analyze even
more general “double circles”, defined as follows.

######  Definition 35.

Let $N_{1},\dots,N_{m}\geq 0$ be integers, at least one non-zero. Then, the
corresponding _generalized double circle_ (with $n=1N_{1}+2N_{2}+\dots+mN_{m}$
chain edges) is the chain

$C_{\mathsf{gdc}}(N_{1},\dots,N_{m})=C_{\mathsf{poly}}(C_{\mathsf{cvx}}(1),N_{1})\vee
C_{\mathsf{poly}}(C_{\mathsf{cvx}}(2),N_{2})\vee\dots\vee
C_{\mathsf{poly}}(C_{\mathsf{cvx}}(m),N_{m}),$

where we simply omit the poly-$C_{\mathsf{cvx}}(k)$ chains with $N_{k}=0$.

######  Theorem 36.

Let $N=N_{1}+\dots+N_{m}$. There is a constant $c_{m}$ depending only on $m$
such that

$U(C_{\mathsf{gdc}}(N_{1},\dots,N_{m}))\geq\frac{1}{(N+1)^{c_{m}}}\prod_{k=1}^{m}\Big{(}2^{k}(k+1)\Big{)}^{N_{k}}.$

###### Proof.

By Corollary 25 and Lemma 22, we get

$U(C_{\mathsf{gdc}}(N_{1},\dots,N_{m}))\geq\prod_{k=1}^{m}U(C_{\mathsf{poly}}(C_{\mathsf{cvx}}(k),N_{k})).$

Asinowski, Krattenthaler, and Mansour [8] show for any fixed $k$ that

$U(C_{\mathsf{poly}}(C_{\mathsf{cvx}}(k),M))=\widetilde{\Omega}((2^{k}(k+1))^{M})\hskip
28.45274pt\text{(as $M\to\infty$)},$

implying the existence of an absolute constant $d_{k}$ such that

$U(C_{\mathsf{poly}}(C_{\mathsf{cvx}}(k),M))\geq\frac{1}{(M+1)^{d_{k}}}\cdot(2^{k}(k+1))^{M}\hskip
28.45274pt\text{(for all $M\geq 1$)}.$

Substituting the respective $N_{k}$ for $M$ and defining
$c_{m}=d_{1}+\dots+d_{m}$ concludes the proof. ∎

#### Second improvement.

The authors of [12] use numerical optimization in the final step of analyzing
generalized double zig-zag chains. We solve the corresponding optimization
problem algebraically, via Lagrange multipliers. This is best captured by the
following lemma.

######  Lemma 37.

Let $u_{1},\dots,u_{m}\geq 0$ be given and let
$H(\alpha_{1},\dots,\alpha_{m})=-\sum_{k=1}^{m}\alpha_{k}\cdot\ln(\alpha_{k})$
be the entropy function. Then,

$\max_{\begin{subarray}{c}0\leq\alpha_{1},\dots,\alpha_{m}\leq 1\\\
\alpha_{1}+\dots+\alpha_{m}=1\end{subarray}}e^{H(\alpha_{1},\dots,\alpha_{m})}\cdot\prod_{k=1}^{m}u_{k}^{\alpha_{k}}=\sum_{k=1}^{m}u_{k}.$

###### Proof.

Without loss of generality, assume that $u_{k}>0$ for all $k$ (otherwise put
$\alpha_{k}=0$, after which we are left with the same proof for a smaller
number $m$ of variables). To simplify notation, define

$f(\alpha_{1},\dots,\alpha_{m}):=e^{H(\alpha_{1},\dots,\alpha_{m})}\cdot\prod_{k=1}^{m}u_{k}^{\alpha_{k}}.$

The proof is by induction on $m$. If $m=1$, then $\alpha_{1}=1$ and the
statement is trivial. For $m\geq 2$, note that the maximum of $f$ always
exists since we are maximizing over a compact region.

Let us now consider the boundary first. If $\alpha_{i}=0$ for some index $i$,
then by induction

$\max_{\begin{subarray}{c}0\leq\alpha_{1},\dots,\alpha_{m}\leq 1\\\
\alpha_{1}+\dots+\alpha_{m}=1\\\
\alpha_{i}=0\end{subarray}}f(\alpha_{1},\dots,\alpha_{m})=\sum_{k=1}^{m}u_{k}-u_{i}\leq\sum_{k=1}^{m}u_{k}.$

On the other hand, if $\alpha_{i}=1$ for some $i$, then $\alpha_{j}=0$ for all
other indices $j$ and the same argument applies. To summarize, if the maximum
is on the boundary, then it is at most $u_{1}+\dots+u_{k}$.

Let us now consider the interior. After taking logs, we are left to show that

$\max_{\begin{subarray}{c}0<\alpha_{1},\dots,\alpha_{m}<1\\\
\alpha_{1}+\dots+\alpha_{m}=1\end{subarray}}\ln(f(\alpha_{1},\dots,\alpha_{m}))=\ln\Big{(}\sum_{k=1}^{m}u_{k}\Big{)}.$

By making use of the definitions

$\displaystyle g(\alpha_{1},\dots,\alpha_{m})$
$\displaystyle:=\ln(f(\alpha_{1},\dots,\alpha_{m}))=H(\alpha_{1},\dots,\alpha_{m})+\sum_{k=1}^{m}\alpha_{k}\cdot\ln(u_{k}),$
$\displaystyle h(\alpha_{1},\dots,\alpha_{m})$
$\displaystyle:=\alpha_{1}+\dots+\alpha_{m}-1,$

we see that, equivalently, we are maximizing $g$ over the open set
$0<\alpha_{1},\dots,\alpha_{m}<1$ under the constraint
$h(\alpha_{1},\dots,\alpha_{m})=0$. By Lagrange multipliers, any such maximum
$(\alpha_{1},\dots,\alpha_{m})$, if it exists, has to solve

$\frac{\partial g}{\partial\alpha_{k}}=\lambda\cdot\frac{\partial
h}{\partial\alpha_{k}}$

for some $\lambda\in\mathbb{R}$ and all $k=1,\dots,m$. For our concrete
functions $g$ and $h$, these equations are

$-\ln(\alpha_{k})-1+\ln(u_{k})=\lambda$

or, equivalently,

$\alpha_{k}=e^{-\lambda-1}\cdot u_{k}.$

Plugging this into the constraint $\alpha_{1}+\dots+\alpha_{m}=1$ yields

$e^{-\lambda-1}\cdot(u_{1}+\dots+u_{m})=1,$

which then allows us to eliminate $\lambda$ and we arrive at

$\alpha_{k}=\frac{1}{u_{1}+\dots+u_{m}}\cdot u_{k}.$

For these particular values $\alpha_{k}$, we now calculate

$\displaystyle g(\alpha_{1},\dots,\alpha_{m})$
$\displaystyle=H(\alpha_{1},\dots,\alpha_{m})+\sum_{k=1}^{m}\alpha_{k}\cdot\ln(u_{k})$
$\displaystyle=-\sum_{k=1}^{m}\frac{u_{k}}{u_{1}+\dots+u_{m}}\cdot\ln\Big{(}\frac{u_{k}}{u_{1}+\dots+u_{m}}\Big{)}+\sum_{k=1}^{m}\frac{u_{k}}{u_{1}+\dots+u_{m}}\cdot\ln(u_{k})$
$\displaystyle=\sum_{k=1}^{m}\frac{u_{k}}{u_{1}+\dots+u_{m}}\cdot\Big{(}-\ln\Big{(}\frac{u_{k}}{u_{1}+\dots+u_{m}}\Big{)}+\ln(u_{k})\Big{)}$
$\displaystyle=\sum_{k=1}^{m}\frac{u_{k}}{u_{1}+\dots+u_{m}}\cdot\ln(u_{1}+\dots+u_{m})$
$\displaystyle=\ln(u_{1}+\dots+u_{m})$

and, hence, $f(\alpha_{1},\dots,\alpha_{m})=u_{1}+\dots+u_{m}$. Given that
this value is at least as large as what we got for the boundary, there has to
be a maximum in the interior. By Lagrange multipliers, that maximum has to be
at the values $\alpha_{k}$ we just considered. ∎

#### Third improvement.

Finally, we define a special generating function that behaves well with
regards to convex sums. This will allow us to prove a matching upper bound for
Theorem 36.

######  Definition 38.

Let $C$ be any chain with $n$ chain edges. The _upper triangulation generating
function of $C$_ is defined as

$\phi_{C}(x)=T_{C}(x)-\Big{(}\frac{x}{1-x}\Big{)}^{n+1}T_{C}(1-x).$

Note that $\phi_{C}(x)$ is a rational function. As a formal power series, it
satisfies $\phi_{C}(x)=T_{C}(x)+O(x^{n+1})$. In other words, for
$k=0,\dots,n$, the coefficient of $x^{k}$ in the Taylor expansion of
$\phi_{C}(x)$ at $x=0$ is equal to the triangulation number $t_{k}(C)$.

######  Lemma 39.

For any two chains $C_{1}$ and $C_{2}$, we have

$\phi_{C_{1}\vee
C_{2}}(x)=\frac{1-x}{1-2x}\cdot\phi_{C_{1}}(x)\cdot\phi_{C_{2}}(x).$

The proof of Lemma 39 is deferred to the next subsection since it involves
some tedious computations. Here, we focus on the following implication.

######  Theorem 40.

For the generalized double circle, we have

$U(C_{\mathsf{gdc}}(N_{1},\dots,N_{m}))\leq\prod_{k=1}^{m}(2^{k}(k+1))^{N_{k}}.$

###### Proof.

First, by repeated invocation of Lemma 39, we get

$\phi_{C_{\mathsf{gdc}}(N_{1},\dots,N_{m})}(x)=\Big{(}\frac{1-x}{1-2x}\Big{)}^{N_{1}+\dots+N_{m}-1}\cdot\prod_{k=1}^{m}\Big{(}\phi_{C_{\mathsf{ccv}}(k)}(x)\Big{)}^{N_{k}}.$

Second, recall that for concave chains we have $T_{C_{\mathsf{ccv}}(k)}(x)=1$.
Therefore, by definition of $\phi$ and by the geometric series,

$\phi_{C_{\mathsf{ccv}}(k)}(x)=1-\Big{(}\frac{x}{1-x}\Big{)}^{k+1}=\frac{1-2x}{1-x}\cdot\sum_{i=0}^{k}\Big{(}\frac{x}{1-x}\Big{)}^{i}.$

Third, for all $n\geq 2$ and $k\geq 0$ we have the combinatorial identity

$[x^{n-1}]\Big{(}\frac{x}{1-x}\Big{)}^{k}=\binom{n-2}{k-1}<2^{n}.$

With $n=1N_{1}+2N_{2}+\dots+mN_{m}$ being the number of chain edges, we can
now combine these three ingredients and get

$\displaystyle U(C_{\mathsf{gdc}}(N_{1},\dots,N_{m}))$
$\displaystyle=[x^{n-1}]\phi_{C_{\mathsf{gdc}}(N_{1},\dots,N_{m})}(x)$
$\displaystyle=[x^{n-1}]\Big{(}\frac{1-x}{1-2x}\Big{)}^{N_{1}+\dots+N_{m}-1}\cdot\prod_{k=1}^{m}\Big{(}\phi_{C_{\mathsf{ccv}}(k)}(x)\Big{)}^{N_{k}}$
$\displaystyle=[x^{n-1}]\frac{1-2x}{1-x}\prod_{k=1}^{m}\Bigg{(}\sum_{i=0}^{k}\Big{(}\frac{x}{1-x}\Big{)}^{i}\Bigg{)}^{\;\mathclap{N_{k}}}$
$\displaystyle\leq[x^{n-1}]\prod_{k=1}^{m}\Bigg{(}\sum_{i=0}^{k}\Big{(}\frac{x}{1-x}\Big{)}^{i}\Bigg{)}^{\;\mathclap{N_{k}}}\leq
2^{n}\prod_{k=1}^{m}(k+1)^{N_{k}},$

where expanding the second to last term yields $\prod_{k}(k+1)^{N_{k}}$
summands, each some power of $\frac{x}{1-x}$, for which the coefficient of
$x^{n-1}$ is always less than $2^{n}$. ∎

###  4.2 Proof of Lemma 39

First, let us consider the simpler case where $C_{1}=C_{\mathsf{ccv}}(n_{1})$
and $C_{2}=C_{\mathsf{ccv}}(n_{2})$ for arbitrary integers $n_{1},n_{2}\geq
1$. As already seen in the previous subsection, in such a case we have

$\phi_{C_{\mathsf{ccv}}(n_{i})}(x)=1-\Big{(}\frac{x}{1-x}\Big{)}^{n_{i}+1}.$

In the paragraph after Lemma 24, we have further seen that

$T_{C_{\mathsf{ccv}}(n_{1})\,\vee\,C_{\mathsf{ccv}}(n_{2})}(x)=1+\sum_{l=1}^{n_{1}}\sum_{r=1}^{n_{2}}\binom{l+r-2}{l-1}x^{l+r-1}.$

Therefore, in order to prove Lemma 39 for this specific choice of $C_{1}$ and
$C_{2}$, it suffices to show the following identity.

######  Proposition 41.

Let $n_{1},n_{2}\geq 0$. Define the formal power series

$\displaystyle T_{n_{1},n_{2}}(x)$
$\displaystyle:=1+\sum_{l=1}^{n_{1}}\sum_{r=1}^{n_{2}}\binom{l+r-2}{l-1}x^{l+r-1}=1+\sum_{l=0}^{n_{1}-1}\sum_{r=0}^{n_{2}-1}\binom{l+r}{l}x^{l+r+1},$
$\displaystyle L_{n_{1},n_{2}}(x)$
$\displaystyle:=T_{n_{1},n_{2}}(x)-\left(\frac{x}{1-x}\right)^{n_{1}+n_{2}+1}T_{n_{1},n_{2}}(1-x),$
$\displaystyle R_{n_{1},n_{2}}(x)$
$\displaystyle:=\frac{1-x}{1-2x}\cdot\left(1-\left(\frac{x}{1-x}\right)^{n_{1}+1}\right)\cdot\left(1-\left(\frac{x}{1-x}\right)^{n_{2}+1}\right).$

Then, we have that $L_{n_{1},n_{2}}(x)=R_{n_{1},n_{2}}(x)$.

###### Proof.

We use induction on $(n_{1},n_{2})$. If at least one of $n_{1}$ and $n_{2}$ is
zero, then the proposition follows easily. We may hence assume that
$n_{1},n_{2}\geq 1$.

First, we do some computations with $T_{n_{1},n_{2}}(x)$. We use the letter
$k$ to denote the sum $l+r$, and we also use Iverson brackets to simplify
notation.

$\displaystyle T_{n_{1},n_{2}}(x)$
$\displaystyle=1+\sum_{k=0}^{\infty}\sum_{l+r=k}[0\leq l<n_{1},0\leq
r<n_{2}]\binom{k}{l}x^{k+1}$
$\displaystyle=1+\sum_{k=0}^{\infty}2^{k}x^{k+1}-\sum_{k=n_{1}}^{\infty}\sum_{l=n_{1}}^{k}\binom{k}{l}x^{k+1}-\sum_{k=n_{2}}^{\infty}\sum_{r=n_{2}}^{k}\binom{k}{r}x^{k+1}+\sum_{l=n_{1}}^{\infty}\sum_{r=n_{2}}^{\infty}\binom{l+r}{l}x^{l+r+1}$
$\displaystyle=1+\frac{x}{1-2x}-\sum_{l=n_{1}}^{\infty}\sum_{k=l}^{\infty}\binom{l+(k-l)}{l}x^{k+1}-\sum_{r=n_{2}}^{\infty}\sum_{k=r}^{\infty}\binom{r+(k-r)}{r}x^{k+1}+\sum_{l}\sum_{r}(\dots)$
$\displaystyle=\frac{1-x}{1-2x}-\sum_{l=n_{1}}^{\infty}\left(\frac{x}{1-x}\right)^{l+1}-\sum_{r=n_{2}}^{\infty}\left(\frac{x}{1-x}\right)^{r+1}+\sum_{l}\sum_{r}(\dots)$
$\displaystyle=\frac{1-x}{1-2x}-\left(\frac{x}{1-x}\right)^{n_{1}+1}\frac{1}{1-\frac{x}{1-x}}-\left(\frac{x}{1-x}\right)^{n_{2}+1}\frac{1}{1-\frac{x}{1-x}}+\sum_{l}\sum_{r}(\dots)$
$\displaystyle=\frac{1-x}{1-2x}\left(1-\left(\frac{x}{1-x}\right)^{n_{1}+1}-\left(\frac{x}{1-x}\right)^{n_{2}+1}\right)+\sum_{l=n_{1}}^{\infty}\sum_{r=n_{2}}^{\infty}\binom{l+r}{l}x^{l+r+1}$

We can now use the above equation in order to compute the following
expression.

$\displaystyle
T_{n_{1},n_{2}}(x)-\frac{x}{1-x}\left(T_{n_{1}-1,n_{2}}(x)+T_{n_{1},n_{2}-1}(x)\right)+\left(\frac{x}{1-x}\right)^{2}T_{n_{1}-1,n_{2}-1}(x)$
$\displaystyle=\;$
$\displaystyle\frac{1-2x}{1-x}+\frac{1}{(1-x)^{2}}\sum_{l=n_{1}}^{\infty}\sum_{r=n_{2}}^{\infty}\bigg{[}(1-x)^{2}\binom{l+r}{l}-(1-x)\binom{l+r-1}{l}$
$\displaystyle\hskip
113.81102pt-(1-x)\binom{l+r-1}{l-1}+\binom{l+r-2}{l-1}\bigg{]}\cdot x^{l+r+1}$
$\displaystyle=\;$
$\displaystyle\frac{1-2x}{1-x}+\frac{1}{(1-x)^{2}}\sum_{l=n_{1}}^{\infty}\sum_{r=n_{2}}^{\infty}\bigg{[}x^{2}\binom{l+r}{l}-x\binom{l+r-1}{l}$
$\displaystyle\hskip
113.81102pt-x\binom{l+r-1}{l-1}+\binom{l+r-2}{l-1}\bigg{]}\cdot x^{l+r+1}$
$\displaystyle=\;$
$\displaystyle\frac{1-2x}{1-x}+\frac{1}{(1-x)^{2}}\sum_{l\in\mathbb{Z}}\sum_{r\in\mathbb{Z}}\binom{l+r-2}{l-1}\bigg{(}[l>n_{1},r>n_{2}]-[l>n_{1},r\geq
n_{2}]$ $\displaystyle\hskip 113.81102pt-[l\geq n_{1},r>n_{2}]+[l\geq
n_{1},r\geq n_{2}]\bigg{)}\cdot x^{l+r+1}$ $\displaystyle=\;$
$\displaystyle\frac{1-2x}{1-x}+\frac{1}{(1-x)^{2}}\sum_{l\in\mathbb{Z}}\sum_{r\in\mathbb{Z}}\binom{l+r-2}{l-1}[l=n_{1},r=n_{2}]\cdot
x^{l+r+1}$ $\displaystyle=\;$
$\displaystyle\frac{1-2x}{1-x}+\frac{1}{(1-x)^{2}}\binom{n_{1}+n_{2}-2}{n_{1}-1}x^{n_{1}+n_{2}+1}$

In turn, we can further use the above to compute a very similar expression for
$L_{n_{1},n_{2}}(x)$, noting that the second term from before cancels nicely
in the very last step.

$\displaystyle
L_{n_{1},n_{2}}(x)-\frac{x}{1-x}\left(L_{n_{1}-1,n_{2}}(x)+L_{n_{1},n_{2}-1}(x)\right)+\left(\frac{x}{1-x}\right)^{2}L_{n_{1}-1,n_{2}-1}(x)$
$\displaystyle=\;$ $\displaystyle
T_{n_{1},n_{2}}(x)-\frac{x}{1-x}\left(T_{n_{1}-1,n_{2}}(x)+T_{n_{1},n_{2}-1}(x)\right)+\left(\frac{x}{1-x}\right)^{2}T_{n_{1}-1,n_{2}-1}(x)$
$\displaystyle\quad-\left(\frac{x}{1-x}\right)^{n_{1}+n_{2}+1}\binom{n_{1}+n_{2}-2}{n_{1}-1}(1-x)^{n_{1}+n_{2}-1}=\frac{1-2x}{1-x}$

On the other hand, a direct computation shows that we also have the same
equation for $R_{n_{1},n_{2}}(x)$.

$R_{n_{1},n_{2}}(x)-\frac{x}{1-x}\left(R_{n_{1}-1,n_{2}}(x)+R_{n_{1},n_{2}-1}(x)\right)+\left(\frac{x}{1-x}\right)^{2}R_{n_{1}-1,n_{2}-1}(x)=\frac{1-2x}{1-x}$

Therefore, the proposition now easily follows by combining the previous two
equations with the induction hypothesis. ∎

Let now $C_{1}$ and $C_{2}$ be two arbitrary chains with $n_{1}$ and $n_{2}$
chain edges, respectively. By making use of Lemma 24 and the special case of
Lemma 39 that we just proved in Proposition 41, we can now compute

$\displaystyle\phi_{C_{1}\vee C_{2}}(x)$ $\displaystyle=T_{C_{1}\vee
C_{2}}(x)+\Big{(}\frac{x}{1-x}\Big{)}^{n_{1}+n_{2}+1}T_{C_{1}\vee C_{2}}(1-x)$
$\displaystyle=\sum_{k_{1}=0}^{n_{1}-1}\sum_{k_{2}=0}^{n_{2}-1}t_{k_{1}}(C_{1})\cdot
t_{k_{2}}(C_{2})\cdot
x^{k_{1}+k_{2}}\Bigg{(}T_{C_{\mathsf{ccv}}(n_{1}-k_{1})\,\vee\,C_{\mathsf{ccv}}(n_{2}-k_{2})}(x)$
$\displaystyle\hskip
56.9055pt+\Big{(}\frac{x}{1-x}\Big{)}^{n_{1}+n_{2}+1-k_{1}-k_{2}}\cdot
T_{C_{\mathsf{ccv}}(n_{1}-k_{1})\,\vee\,C_{\mathsf{ccv}}(n_{2}-k_{2})}(1-x)\Bigg{)}$
$\displaystyle=\sum_{k_{1}=0}^{n_{1}-1}\sum_{k_{2}=0}^{n_{2}-1}t_{k_{1}}(C_{1})\cdot
t_{k_{2}}(C_{2})\cdot
x^{k_{1}+k_{2}}\cdot\phi_{C_{\mathsf{ccv}}(n_{1}-k_{1})\,\vee\,C_{\mathsf{ccv}}(n_{2}-k_{2})}(x)$
$\displaystyle=\sum_{k_{1}=0}^{n_{1}-1}\sum_{k_{2}=0}^{n_{2}-1}t_{k_{1}}(C_{1})\cdot
t_{k_{2}}(C_{2})\cdot
x^{k_{1}+k_{2}}\cdot\frac{1-x}{1-2x}\cdot\phi_{C_{\mathsf{ccv}}(n_{1}-k_{1})}(x)\cdot\phi_{C_{\mathsf{ccv}}(n_{2}-k_{2})}(x)$
$\displaystyle=\frac{1-x}{1-2x}\cdot\Big{(}\sum_{k_{1}=0}^{n_{1}-1}t_{k_{1}}(C_{1})\cdot
x^{k_{1}}\cdot\phi_{C_{\mathsf{ccv}}(n_{1}-k_{1})}(x)\Big{)}\cdot\Big{(}\sum_{k_{2}=0}^{n_{2}-1}t_{k_{2}}(C_{2})\cdot
x^{k_{2}}\cdot\phi_{C_{\mathsf{ccv}}(n_{2}-k_{2})}(x)\Big{)}$
$\displaystyle=\frac{1-x}{1-2x}\cdot\phi_{C_{1}}(x)\cdot\phi_{C_{2}}(x).$

###  4.3 Proof of Theorem 30 (Poly Chains)

Recall once more Lemma 24. For the special case where
$C_{2}=C_{\mathsf{ccv}}(n_{2})$, we have that $t_{0}(C_{2})=1$ is the only
non-zero triangulation number, and hence

$T_{C_{1}\vee
C_{\mathsf{ccv}}(n_{2})}(x)=\sum_{k_{1}=0}^{n_{1}-1}t_{k_{1}}(C_{1})\cdot
x^{k_{1}}\cdot
T_{C_{\mathsf{ccv}}(n_{1}-k_{1})\,\vee\,C_{\mathsf{ccv}}(n_{2})}(x).$

After plugging this into the right-hand side of Lemma 24, we get the following
variant of the statement, where the second sum is left unexpanded.

######  Lemma 42.

Let $C_{1}$ be a chain with $n_{1}$ chain edges and let $C_{2}$ be any chain.
Then,

$T_{C_{1}\vee C_{2}}(x)=\sum_{k=0}^{n_{1}-1}t_{k}(C_{1})\cdot x^{k}\cdot
T_{C_{\mathsf{ccv}}(n_{1}-k)\,\vee\,C_{2}}(x).$

Let now $C_{0}$ be any fixed chain with $m$ chain edges and let $N\geq 2$.
Using commutativity as in Corollary 26, we can inductively apply Lemma 42 to
the poly-$C_{0}$ chain and get

$T_{C_{\mathsf{poly}}(C_{0},N)}=\sum_{k_{1}=0}^{m-1}\dots\sum_{k_{N}=0}^{m-1}t_{k_{1}}(\overline{C_{0}})\cdots
t_{k_{N}}(\overline{C_{0}})\cdot x^{k_{1}+\dots+k_{N}}\cdot
T_{C_{\mathsf{ccv}}(m-k_{1})\,\vee\,\dots\vee\,C_{\mathsf{ccv}}(m-k_{N})}(x).$

For any particular summand in the above expression, let $a_{i}$ be the number
of indices $j=1,\dots,N$ that satisfy $k_{j}=m-i$. Then, this particular
summand can also be written as

$t_{0}(\overline{C_{0}})^{a_{m}}\cdot t_{1}(\overline{C_{0}})^{a_{m-1}}\cdots
t_{m-1}(\overline{C_{0}})^{a_{1}}\cdot
x^{0a_{m}+1a_{m-1}+\dots+(m-1)a_{1}}\cdot
T_{C_{\mathsf{gdc}}(a_{1},\dots,a_{m})}(x).$

Since the number of summands with these particular values $a_{i}$ is equal to
$\binom{N}{a_{1},\dots,a_{m}}$, we hence get

$T_{C_{\mathsf{poly}}(C_{0},N)}(x)=\sum_{\begin{subarray}{c}0\leq
a_{1},\dots,a_{m}\leq N\\\
a_{1}+\dots+a_{m}=N\end{subarray}}\binom{N}{a_{1},\dots,a_{m}}\cdot\Bigg{(}\prod_{k=1}^{m}t_{m-k}(\overline{C_{0}})^{a_{k}}\cdot
x^{(m-k)a_{k}}\Bigg{)}\cdot T_{C_{\mathsf{gdc}}(a_{1},\dots,a_{m})}(x).$

Finally, note that the corresponding leading coefficients on both sides are
equal to

$U(C_{\mathsf{poly}}(C_{0},N))=\sum_{\begin{subarray}{c}0\leq
a_{1},\dots,a_{m}\leq N\\\
a_{1}+\dots+a_{m}=N\end{subarray}}\binom{N}{a_{1},\dots,a_{m}}\cdot\Bigg{(}\prod_{k=1}^{m}t_{m-k}(\overline{C_{0}})^{a_{k}}\Bigg{)}\cdot
U(C_{\mathsf{gdc}}(a_{1},\dots,a_{m})).$

We will now use this equation to prove both an upper and a lower bound for
$U(C_{\mathsf{poly}}(C_{0},N))$.

#### Upper bound.

By Theorem 40 and the multinomial theorem, we get

$\displaystyle U(C_{\mathsf{poly}}(C_{0},N))$
$\displaystyle\leq\sum_{\begin{subarray}{c}0\leq a_{1},\dots,a_{m}\leq N\\\
a_{1}+\dots+a_{m}=N\end{subarray}}\binom{N}{a_{1},\dots,a_{m}}\cdot\prod_{k=1}^{m}\Big{(}t_{m-k}(\overline{C_{0}})\cdot
2^{k}(k+1)\Big{)}^{a_{k}}$
$\displaystyle=\Bigg{(}\sum_{k=1}^{m}t_{m-k}(\overline{C_{0}})\cdot
2^{k}(k+1)\Bigg{)}^{N}.$

The claimed upper bound now follows by recalling that the poly-$C_{0}$ chain
has $n=Nm$ chain edges.

#### Lower bound.

The entropy bound for multinomial coefficients states that

$\binom{N}{a_{1},\dots,a_{m}}\geq\frac{1}{N^{m}}e^{H(\frac{a_{1}}{N},\dots,\frac{a_{m}}{N})},\qquad
H(\alpha_{1},\dots,\alpha_{m})=-\sum_{k=1}^{m}\alpha_{k}\ln(\alpha_{k}).$

By Theorem 36 and the above entropy bound, we get for some constant $c_{m}$
that

$\displaystyle U(C_{\mathsf{poly}}(C_{0},N))$
$\displaystyle\geq\frac{1}{(N+1)^{c_{m}}}\sum_{\begin{subarray}{c}0\leq
a_{1},\dots,a_{m}\leq N\\\
a_{1}+\dots+a_{m}=N\end{subarray}}\binom{N}{a_{1},\dots,a_{m}}\cdot\prod_{k=1}^{m}\Big{(}t_{m-k}(\overline{C_{0}})\cdot
2^{k}(k+1)\Big{)}^{a_{k}}$
$\displaystyle\geq\frac{1}{(N+1)^{c_{m}+m}}\sum_{\begin{subarray}{c}0\leq
a_{1},\dots,a_{m}\leq N\\\
a_{1}+\dots+a_{m}=N\end{subarray}}e^{H(\frac{a_{1}}{N},\dots,\frac{a_{m}}{N})}\cdot\prod_{k=1}^{m}\Big{(}t_{m-k}(\overline{C_{0}})\cdot
2^{k}(k+1)\Big{)}^{a_{k}}.$

We can lower bound the right hand side by picking any one summand. We pick the
largest one by using Lemma 37 (we might have to round the $a_{k}$ slightly to
get integer values, but the effect of this vanishes as $N$ goes to infinity).
As desired, the resulting lower bound is therefore

$U(C_{\mathsf{poly}}(C_{0},N))=\Omega\Bigg{(}\frac{1}{(N+1)^{c_{m}+m}}\Bigg{(}\sum_{k=1}^{m}t_{m-k}(\overline{C_{0}})\cdot
2^{k}(k+1)\Bigg{)}^{N}\Bigg{)}\hskip 28.45274pt\text{(as $N\to\infty$)}.$

###  4.4 Proof of Theorem 30 (Twin Chains)

Let $C_{0}$ again be any fixed chain with $m$ chain edges and let $N\geq 2$.
Observe then with Lemma 22 that we have in fact
$T_{\overline{C_{\mathsf{poly}}(C_{0},N)}}(x)=T_{C_{0}}(x)^{N}$ for the
flipped poly-$C_{0}$ chains. Therefore, expanding the right hand side with the
multinomial theorem yields the coefficients

$\gamma_{k,N}:=t_{k}(\overline{C_{\mathsf{poly}}(C_{0},N)})=\sum_{\begin{subarray}{c}0\leq
a_{1},\dots,a_{m}\leq N\\\ a_{1}+\dots+a_{m}=N\\\
(m-1)a_{1}+\dots+a_{m-1}=k\end{subarray}}\binom{N}{a_{1},\dots,a_{m}}\prod_{\ell=1}^{m}t_{m-\ell}(C_{0})^{a_{\ell}}.$

On the other hand, applying Lemma 42 twice to the twin-$C_{0}$ chains yields

$T_{C_{\mathsf{twin}}(C_{0},N)}=\sum_{k_{1}=0}^{mN-1}\sum_{k_{2}=0}^{mN-1}\gamma_{k_{1},N}\cdot\gamma_{k_{2},N}\cdot
x^{k_{1}+k_{2}}\cdot T_{C_{\mathsf{ccv}}(mN-k_{1})\vee E\vee
C_{\mathsf{ccv}}(mN-k_{2})}(x),$

with leading coefficients

$\displaystyle U({C_{\mathsf{twin}}(C_{0},N)})$
$\displaystyle=\sum_{k_{1}=0}^{mN-1}\sum_{k_{2}=0}^{mN-1}\gamma_{k_{1},N}\cdot\gamma_{k_{2},N}\cdot
U({C_{\mathsf{ccv}}(mN-k_{1})\vee E\vee C_{\mathsf{ccv}}(mN-k_{2})})$
$\displaystyle=\sum_{k_{1}=0}^{mN-1}\sum_{k_{2}=0}^{mN-1}\gamma_{k_{1},N}\cdot\gamma_{k_{2},N}\cdot\binom{2mN-
k_{1}-k_{2}}{mN-k_{1}},$

where the last step is the same as in the analysis of the classic double
chain, see [17]. We will again use the above equation to prove both an upper
and a lower bound for $U({C_{\mathsf{twin}}(C_{0},N)})$.

#### Upper bound.

After bounding the binomial coefficient by $2^{2mN-k_{1}-k_{2}}$, we can
factorize to

$U({C_{\mathsf{twin}}(C_{0},N)})\leq\Bigg{(}\sum_{k=0}^{mN-1}\gamma_{k,N}\cdot
2^{mN-k}\Bigg{)}^{2}.$

Plugging in the definition of $\gamma_{k,N}$ and noting that
$mN-k=1a_{1}+2a_{2}+\dots+ma_{m}$, we can again simplify with the multinomial
theorem, similar to what we did for poly-$C_{0}$ chains, and get

$U({C_{\mathsf{twin}}(C_{0},N)})\leq\Bigg{(}\sum_{k=1}^{m}t_{m-k}(C_{0})\cdot
2^{k}\Bigg{)}^{2N}.$

#### Lower bound.

By only keeping terms with $k_{1}=k_{2}$, we get

$\displaystyle U({C_{\mathsf{twin}}(C_{0},N)})$
$\displaystyle\geq\sum_{k=0}^{mN-1}\gamma_{k,N}^{2}\cdot\binom{2mN-2k}{mN-k}$
$\displaystyle\geq\sum_{k=0}^{mN-1}\gamma_{k,N}^{2}\cdot\frac{2^{2mN-2k}}{2mN}=\frac{4^{mN}}{2mN}\sum_{k=0}^{mN-1}\Big{(}2^{-k}\cdot\gamma_{k,N}\Big{)}^{2}.$

By dropping all the summands except for one specific $k$ to be determined
later, and by plugging in the definition of $\gamma_{k,N}$ and again noting
that $mN-k=1a_{1}+2a_{2}+\dots+ma_{m}$, we get

$\displaystyle U({C_{\mathsf{twin}}(C_{0},N)})$
$\displaystyle\geq\frac{4^{mN}}{2mN}\Big{(}2^{-k}\cdot\gamma_{k,N}\Big{)}^{2}=\frac{1}{2mN}\Big{(}2^{mN-k}\cdot\gamma_{k,N}\Big{)}^{2}$
$\displaystyle=\frac{1}{2mN}\Bigg{(}\sum_{\begin{subarray}{c}0\leq
a_{1},\dots,a_{m}\leq N\\\ a_{1}+\dots+a_{m}=N\\\
(m-1)a_{1}+\dots+a_{m-1}=k\end{subarray}}\binom{N}{a_{1},\dots,a_{m}}\prod_{\ell=1}^{m}\Big{(}t_{m-\ell}(C_{0})\cdot
2^{\ell}\Big{)}^{a_{\ell}}\Bigg{)}^{2}.$

After applying the entropy bound, we pick the largest summand for the best
possible $k$ via Lemma 37, and get

$\displaystyle
U({C_{\mathsf{twin}}(C_{0},N)})=\Omega\Bigg{(}\frac{1}{2mN^{m+1}}\Bigg{(}\sum_{\ell=1}^{m}t_{m-\ell}(C_{0})\cdot
2^{\ell}\Bigg{)}^{2N}\Bigg{)}\hskip 28.45274pt\text{(as $N\to\infty$)}.$

### Acknowledgments

The material presented in this paper originates from the first author’s
Master’s thesis [18] under the second author’s direct supervision. Both
authors wish to express their gratitude to Emo Welzl, the official advisor in
this endeavor.

## References

  * [1] OEIS Foundation Inc. (2021).  The on-line encyclopedia of integer sequences.  https://oeis.org/A000108.  Catalan numbers.
  * [2] OEIS Foundation Inc. (2021).  The on-line encyclopedia of integer sequences.  https://oeis.org/A006318.  Large Schröder numbers.
  * [3] OEIS Foundation Inc. (2021).  The on-line encyclopedia of integer sequences.  https://oeis.org/A001003.  Little Schröder numbers.
  * [4] Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber.  An improved lower bound on the minimum number of triangulations.  In Proceedings of the 32nd International Symposium on Computational Geometry, 2016.
  * [5] Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, and Birgit Vogtenhuber.  On the number of plane geometric graphs.  Graphs Comb., 23(Supplement-1):67–84, 2007.
  * [6] Miklós Ajtai, Václav Chvátal, Monroe M. Newborn, and Endre Szemerédi.  Crossing-free subgraphs.  In Theory and Practice of Combinatorics, volume 60 of North-Holland Mathematics Studies, pages 9–12. North-Holland, 1982.
  * [7] Victor Alvarez and Raimund Seidel.  A simple aggregative algorithm for counting triangulations of planar point sets and related problems.  In Proceedings of the 29th the Symposium on Computational Geometry, 2013.
  * [8] Andrei Asinowski, Christian Krattenthaler, and Toufik Mansour.  Counting triangulations of some classes of subdivided convex polygons.  Eur. J. Comb., 62:92–114, 2017.
  * [9] David Avis and Komei Fukuda.  Reverse search for enumeration.  Discret. Appl. Math., 65(1-3):21–46, 1996.
  * [10] Sergei Bespamyatnikh.  An efficient algorithm for enumeration of triangulations.  Comput. Geom., 23(3):271–279, 2002.
  * [11] Markus Denny and Christian Sohler.  Encoding a triangulation as a permutation of its point set.  In Proceedings of the 9th Canadian Conference on Computational Geometry, 1997.
  * [12] Adrian Dumitrescu, André Schulz, Adam Sheffer, and Csaba D. Tóth.  Bounds on the maximum multiplicity of some common geometric graphs.  SIAM J. Discret. Math., 27(2):802–826, 2013.
  * [13] Peter Epstein and Jörg-Rüdiger Sack.  Generating triangulations at random.  ACM Trans. Model. Comput. Simul., 4(3):267–278, 1994.
  * [14] Jacob E. Goodman and Richard Pollack.  Multidimensional sorting.  SIAM J. Comput., 12(3):484–507, 1983.
  * [15] Ferran Hurtado and Marc Noy.  Counting triangulations of almost-convex polygons.  Ars Comb., 45:169–179, 1997.
  * [16] Dániel Marx and Tillmann Miltzow.  Peeling and nibbling the cactus: Subexponential-time algorithms for counting triangulations and related problems.  In Proceedings of the 32nd International Symposium on Computational Geometry, 2016.
  * [17] Alfredo García Olaverri, Marc Noy, and Javier Tejel.  Lower bounds on the number of crossing-free subgraphs of k${}_{\mbox{n}}$.  Comput. Geom., 16(4):211–221, 2000.
  * [18] Daniel Rutschmann.  On chains and point configurations with many triangulations.  Master’s thesis, ETH Zurich, Zürich, Switzerland, 2021.
  * [19] Francisco Santos and Raimund Seidel.  A better upper bound on the number of triangulations of a planar point set.  J. Comb. Theory, Ser. A, 102(1):186–193, 2003.
  * [20] Raimund Seidel.  On the number of triangulations of planar point sets.  Comb., 18(2):297–299, 1998.
  * [21] Micha Sharir and Adam Sheffer.  Counting triangulations of planar point sets.  Electron. J. Comb., 18(1):1–74, 2011.
  * [22] Micha Sharir and Emo Welzl.  Random triangulations of planar point sets.  In Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006.
  * [23] Warren D. Smith.  Studies in Computational Geometry Motivated by Mesh Generation.  PhD thesis, Princeton University, Princeton, USA, 1989.