Chains, Koch Chains, and Point Sets with many Triangulations

Daniel Rutschmann¹¹1Department of Computer Science, ETH Zürich, Switzerland. E-mail: \url[email protected] Manuel Wettstein²²2Department of Computer Science, ETH Zürich, Switzerland. E-mail: \url[email protected]

(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 [oeiscatalan]. In general, however, this problem turns out to be much more elusive.

There is an elegant algorithm by Alvarez and Seidel [alvarez2013] from 2013 that computes $\mathrm{tr}(P)$ in exponential time $O(2^{n}n^{2})$ . It has been surpassed by Marx and Miltzow [marx2016] in 2016, who showed how to compute $\mathrm{tr}(P)$ in subexponential time $n^{O(\sqrt{n})}$ . Moreover, Avis and Fukuda [avis1996] 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 [bespamyatnikh2002].

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 [ajtai1982] 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 [smith1989, denny1997, seidel1998, santos2003, sharir2006] 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 [sharir2011], 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 [garcia2000] 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. [aichholzer2007] with $\Theta(8.48^{n})$ triangulations and a specific instance of the generalized double zig-zag chain by Dumitrescu, Schulz, Sheffer, and Tóth [dumitrescu2013] 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 [hurtado1997] 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. [aichholzer2016] 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 [goodman1983] 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.

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 [oeisbigschroeder].

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 [epstein1994]. 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.

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 LABEL:sec:polytwin 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.

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.

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}).

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 [oeislittleschroeder] and the number of all chains is given by the large Schröder numbers [oeisbigschroeder].

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.

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.

LABEL:fig:partialexamples 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.