Exact uniform sampling over catalan structures

arXiv:1803.03945v1 [cs.DM] 11 Mar 2018

Alexandros Angelopoulos, Eleni Bakali
Department of Computer Science,
School of Electical and Computer Engineering,
National Technical University of Athens, Greece.

{angelop,mpakali}@corelab.ntua.gr
March 13, 2018

Abstract
We present a new framework for creating elegant algorithms for
exact uniform sampling of important Catalan structures, such as triangulations of convex polygons, Dyck words, monotonic lattice paths and
mountain ranges. Along with sampling, we obtain optimal coding, and
optimal number of random bits required for the algorithm. The framework is based on an original two-parameter recursive relation, where
Ballot and Catalan numbers appear and which may be regarded as
to demonstrate a generalized reduction argument. We then describe
(a) a unique n × n matrix to be used for any of the problems -the
common pre-processing step of our framework- and (b) a linear height
tree, where leaves correspond one by one to all distinct solutions of
each problem; sampling is essentially done by selecting a path from
the root to a leaf - the main algorithm. Our main algorithm is linear
for a number of the problems mentioned.

keywords uniform sampling, optimal coding, catalan structures, convex
triangulations, ballot numbers

1

Introduction

The consideration of different triangulations of a point set first appears in a
well-studied form in the middle of the 18th century by Leonhard Euler: he
successfully conjectured the closed formula for the number of triangulations
of the convex n-gon, that was what we denote now by Cn−2 , the (n − 2)-th
Catalan number. These numbers, named after the Belgian mathematician
Eugène Charles Catalan, satisfy the following basic relations:

1

Cn+1 =

n
X

Ck Cn−k ,

C0 = 1

(1)

k=0

 
2n
1
, C0 = 1
Cn =
n+1 n
4n
4n
Cn ≤ 3/2 √
and
lim
√ =1
n→∞ Cn n3/2 π
n
π

(2)
(3)

They occur as the solution of a very large number of counting problems
in combinatorics. [30] gives more than 200 interpretations, more than 60
exercises, in all, a spectacular volume of work centered around the Catalan
numbers.
Some modern views regarding this core problem is the study of algorithms for efficient coding of triangulations, and for uniform generation or
sampling a random triangulation.
Motivation-Applications. Triangulations of polygons are fundamental structures with many applications e.g. in Computational Geometry
[6, 22], VLSI floorplanning [25], and Graph Drawing [21]. Many algorithms like point location, ray-shooting, visibility area computing and computing shortest paths inside simple polygons, are based on triangulations
[31, 13, 14, 18]. In particular sampling (or equivalently uniform generation)
of random triangulations, apart from its theoretical interest, has many practical applications. Interestingly sampling triangulations was first considered
by physicists for its applications in the study of two dimensional quantum
gravity [3]. Sampling plays a central role in testing and verifying the time
complexity of particular implementations of algorithms like the previously
mentioned, that depend on triangulations. A method to achieve time verification is presented in [10]. Finally efficient coding of triangulations, is
essential for storing them after their random generation, since these data
are usually huge and inefficient coding may cause storing to dominate the
running time of the algorithm that uses these data.
Previous work. There has been significant work on uniform sampling
and coding triangulations, especially since the 1990s [11, 9, 7, 8, 24, 28, 27,
26].
We will mostly compare our results and framework to [8]: Devroye et
al. describe a linear-time algorithm in the RAM model of computation, for
the uniform generation of convex triangulations and monotone lattice paths.
This is actually equivalent to a O(n log n) algorithm, when taking into account that this algorithm needs the generation of O(n) random numbers of
O(log n) bits each. The ballot theorem is invoked in their work (see also
[12], Chapter III), as it describes lattice path problems.
Another line of research regarding triangulations is the study of Markov
chains that move along similar triangulations, most commonly considering as
2

similar those that differ by a single edge flip [16, 20, 19, 23]. These Markov
chains converge to the uniform distribution over the set of triangulations,
thus yielding almost uniform sampling algorithms (this is the well known
Markov chain Monte Carlo method for sampling and counting). The best
of the above mentioned algorithms runs in O(n5 ), but has a deviation ǫ > 0
from the uniform distribution (which is a common drawback/characteristic
of the MCMC method).
While for convex graphs it is the Catalan numbers that give the exact number of triangulations, no such formula exists for a general graph.
Exhaustively enumerating the triangulations is not an easy task: already
Cn = Θ(n−3/2 4n ), while the best known bounds for the generic case are
currently set a lower Ω(2.43n ) ([27]) and an upper O(30n ) ([26]). There is
also no general formula for counting triangulations of convex polygons with
forbidden edges, i.e. when the input is a general graph G embedded to the
plane, and valid triangulations are those that use only edges of G. Naturally,
there has been work on counting the triangulations given a specific point
set asymptotically faster than by enumerating all triangulations ([2]), and
approximately counting with favorable compromises ([1]).

1.1

Our contribution

In this article, we present a unified framework to obtain algorithms for exact
uniform sampling and optimal coding of Catalan structures. We will use the
triangulations of convex polygons as our main problem. We will then use the
monotone lattice path problem to show that our framework can be tweaked
to easily get the very algorithms presented in [8]. In a nutshell, we present:
• new framework and elegant algorithm for exact uniform sampling over
convex triangulations and other Catalan structures;
• new recursive relation for ballot and Catalan numbers with an interesting combinatorial interpretation;
• separate pre-processing step of O(n2 ) time, common to all problems
that can be described by the recursive relation,
• optimal coding of the solutions/samples of the problems: for an input
related to size n, we need exactly log(Cn ) bits to encode each solution;
• optimal number of random bits for the main sampling algorithm: it
needs exactly log Cn random bits to run, i.e. to generate uniformly at
random a solution;
• efficient algorithm for sampling, as well as counting triangulations for
a more general family of graphs embedded to the plane in convex
position: Kn,−m is obtained by an embedding of the complete graph
Kn after removing m consecutive span-2 edges.
3

Although our sampling algorithm has total running time O(n2 ), which
is worse than the O(n log n) of [8], our preprocessing step helps to reduce to
the optitmal the number of random bits needed, as well as the length of the
codewords.
An outline - main ideas Given n, we consider an initial instance which
-in some sense- describes the space of all potential solutions; for instance, in
the case of convex triangulations, we consider the complete convex graph
Kn , as all n(n − 3)/2 diagonals are in our disposal to be selected for some
triangulation, which requires only n − 3 such edges. Our goal is to describe1
a binary tree of polynomial height, with its leaves corresponding one by one
to all triangulations of the convex n-gon and then aim at sampling a leaf
uniformly at random.
In order to achieve this, we need a reduction argument, w.r.t. which the
set of potential solutions on some node’s graph can actually be partitioned
into the solutions obtained either by its left or the right child and which
are disjoint. Then, in order to sample a solution uniformly at random, it
would suffice to be able to calculate the size of each of the two subtrees of
any node [17, 29]. Thus, starting from the root, we should be capable of
uniformly selecting a leaf by recursively selecting one of a node’s children
with probability proportional to the size of the corresponding subtree.
Usually, the estimation of the size of subtrees for an arbitrary tree is
computationally hard [4], and this is the reason that the above method
usually fails. The innovation of our approach consists in that we manage
to construct this tree in a systematic way that not only reflects our reduction argument, but also plenty of isomorphisms are revealed so that (a) the
number of all classes of non-isomorphic instances is polynomial in n (in particular quadratic), and (b) it is easy to determine the class in which each
instance belongs. Eventually, it suffices to solve the general problem only
for a polynomial number of non-isomorphic sub-instances, in a preprocessing
step, bottom-up, in time linear to the number of non-isomorphic instances,
thus in total quadratic in n.
In particular, it occurs that all internal nodes of our tree correspond to
(sub)instances of a more general problem, needing a second parameter to
be described and for which no formula nor algorithm was known until now:
compute the number of triangulations of an embedded to the plane almost
complete convex graph Kn,−m , a graph missing only m consecutive span-2
edges (or ears, as denoted in [15, 8]) from what would be a the complete Kn .
As a first simple note, we get that m ≤ n, thus we have the O(n2 ) classes
of non-isomorphic instances.
In the Sections to follow, we will state and prove properties of the central
1

The construction is done only mentally, for the purposes of the analysis; it is not
actually performed by the algorithm.

4

to our work recursive relation, the sampling algorithm scheme it implies and
its application to convex triangulations and mountain ranges problems (the
latest to be trivially linked also to Dyck words, monotone lattice paths, etc.).

2

Our framework

Let an,m denote the number of solutions corresponding to any problem parameterized by n, m, and consider the following recursive relation:
an,0 = an−1,0 + an,1

(4)

an,m = an−1,m−1 + an,m+1

(5)

a0,0 = 1 and an,n = 0, ∀i ≥ 1

(6)

Theorem 1 Consider the ballot numbers


i+1−j i+1+j
, i, j ≥ 0
Ni,j =
i+1+j
j
Along with defining Ni,−1 = 0, the ballot numbers satisfy 4, 5 and 6 for i = n
and j = n − 1 − m.
In other words, an,m = Nn,n−1−m . Note also that:

 

2n
2n
2
1
an,0 = Nn,n−1 =
=
= Cn
2n n − 1
n+1 n

(7)

We will from now on refer to the relations 4, 5 and 6 as the BC (recursive)
relation or recursion, a naming derived from its close relationship with ballot
and Catalan numbers.
Theorem 2 The generating function for the numbers an,m is
√
(1 − xy)(1 − 1 − 4x − 2xy)
G(x, y) =
2x(1 − y + xy 2 )
Proof. [Proofs of Theorems 1 and 2] The proofs can be found in Appendix
A.

The BC table Immediately, we may define a n × n table/matrix, with
an,m as entries. It can be calculated in O(n2 ) time, bottom-up (Figure 1),
and will be considered as our framework’s pre-processing step. The main
algorithm will simply recall some of its values when needed, in constant
time.
5

n

m

0
1
2
3
4
5
6
7
8
..
.

0
1
1
2
5
14
42
132
429
1430
↑

1

2

0
1
0
3
1
9
4
28
14
90
48
297 165
1001 572

3

4

5

6

7

8

0
1
5
20
75
275

0
1
6
27
110

0
1
7
35

0
1
8

0
1

0

···

..

.

Cn

Figure 1: The BC table. It has (n − 3)(n − 1) + 1 entries. The arrows show
the sequence in which the cells fill up.
The main algorithm scheme Consider now the binary tree implied by
the BC relation (Figure 2), rooted at a node related to an,0 . This means we
are attempting to randomly select one of Cn samples. The BC table allows
us to achieve:
• optimal coding, requiring exactly log(Cn ) = O(n) bits to encode each
solution;
• optimal number of random bits for the main sampling algorithm: generating one random number in the range [0..Cn − 1], which requires
log Cn random bits, suffices.
A common approach is to calculate the sizes of the two sub-trees hanging from some node upon arriving on the very node and branch left or
right with the appropriate probability. This requires a total of (number
of branchings)×(random bits required per branching) random bits. Indeed,
a
≈ 2(n + m),
we may well apply the algorithm of [8], given that n−1,m−1
an,m
the number of random bits needed is O(n log n), as the height of the tree is
linear to n, thus the branchings required to reach a leaf is linear in n, too.
It is evident that establishing the BC table beforehand, and tossing only
log Cn ≈ 4n coins (see (3)) we generate a code uniformly at random, which
uniquely defines the leaf of the tree the algorithm will end upon: we branch
without any more coin tosses, as we know all critical quantities in advance.
Moreover, the scheme allows for down to linear time main algorithms
for sampling an instances, as all leaves’ distance from the root is linear in
n - it actually fluctuates from n to 2n. For instance, we will show that the
6

pr =

pr =

a2,0
a1,0

a2,0
pr =

a1,0

a3,0

a2,0
a3,0

a2,−1
a2,0

pr =

a2,−1

a1,0

a2,−2

pr =

a3,−1
a3,0

a3,−1

a2,0
a3,−1

pr =

a2,0

a1,0

a3,−2

a2,−1

a1,0

a3,−2
a3,−1

a2,−2

a2,−1

a1,0

a3,−3

a2,−2

Figure 2: The universal sampling algorithm scheme: branching with probability analogous to the size of the subtree. The height of the tree is O(n). We
note that typically all an,n nodes are non-existent, as the algorithm branches
towards them with probability 0 - that’s why they are marked red. Also, all
a1,0 labeled nodes have a left child, a0,0 , which is the actual leaf according
to the BC relation.
mountain ranges problem (and, therefore, Dyck words and monotone lattice
paths) has an O(n) main sampling algorithm, which we consider a good
trade-off when we need many samples for the same problem. Remember,
that only a O(n log n) algorithm is proposed in [8].

3

Convex triangulations

As we have already mentioned, for any problem we consider the object which
describes the space of all solutions. In the case of convex triangulations, this
is the complete geometric graph. A geometric graph is defined [5] as a pair
of a point set V on
R2 and a subset of straight line segments withendpoints
V
in V , i.e. E ⊆ 2 . Now let our point set be convex and E = V2 . We may
refer to this special case as the “convex Kn ”, an alternate to the complete
convex geometric graph, taking into account that all convex drawings of Kn
are isomorphic. Some important definitions are the following.
Proper labeling, consecutive vertices and span-2 edges Given a
convex geometrical graph, we will say that its vertex labeling v0 , ..., vn−1 is
proper if its n vertices appear in order, clockwise or counter-clockwise around
its convex hull. We will always assume such a labeling for any convex graph
we refer to, unless noted otherwise. The above being stated, it is evident that

7

for all i ∈ [0..n − 1], vertices vi and vi+1 are consecutive, naturally defining
that vn ≡ v0 . We shall also admit that all edges vi vi+2 , i ∈ [0..n − 1] are
properly defined, as vx ≡ vx mod n , for any x, n.
Let V be a convex point set and assume proper vertex labeling. For
every edge (diagonal) e = vi vj ∈ E, we define its span, denoted by |e|, to be
the minimum distance of its adjacent vertices around the convex hull. The
edges that miss only one vertex, that is edges of the form vi−1 vi+1 , will hold
a key-role in our work, thus we will denote them as span-2 edges. All such
edges can be named after the missed vertex with which they form a triangle:
ei ≡ vi−1 vi+1 .
As an analog to the notion of consecutive vertices, we define two consecutive span-2 edges to be a pair of edges of the form vi−1 vi+1 , vi vi+2 .
Observe that: K3 has no span-2 edges, K4 has two and, for n ≥ 5, Kn
has exactly n of such edges. For n ≥ 5 and any vertex vi , we denote by ei
the span-2 edge vi−1 vi+1 , in other words, the edge that may form a triangle
together with vi .
The Kn,−m graph. We will need to work on specific graphs, that allow for
the desired structure of triangulations to be witnessed. We define Kn,−m to
be the nearly complete convex Kn which misses only m consecutive span-2
edges. Therefore:

• Kn,0 ≡ Kn and when properly defined, Kn,−m has n2 − m edges.

• For n ≥ 5, it is −n ≤ −m ≤ 0, as a graph may miss up to all n span-2
edges.
• The graphs K4,−1 , K4,−2 are properly defined.
• For fixed n, m, all Kn,−m are isomorphic to each other (under rotation).

Proposition 3 Every triangulation of a convex geometric graph on 5 or
more vertices has at least two span-2 edges.
Proof. A triangulation TC on n points requires that all faces but the outer
are triangles. The number of faces f is equal to n − 1 (e.g. use Euler’s
characteristic on plane graphs), therefore there is a total of n − 2 inner
faces/triangles. Since all n non-diagonal edges of TC (the sides of the polygon) are sides of the n − 2 triangles, by the pigeonhole principle, there are
at least 2 triangles which use 2 sides of the n-gon as their sides. Then, those
triangles’ third edge must be an span-2 one and, as soon as n ≥ 5, those
third edges do not coincide.

Proposition 4 A convex geometric graph with n ≥ 5 and only two span-2
edges which appear consecutive in the drawing has no triangulation. Equivalently, T (Kn,−(n−2) ) = 0.
8

Proof.
Two consecutive span-2 edges intersect, therefore together they
do not form any triangulation, unless only one is needed (quadrilateral).
So there must be a third span-2 edge which, together with one of the 2
consecutive ones, is the obligatory second span-2 edge in a triangulation T
of the graph (see Proposition 3). Contradiction, as the graph has no other
such edge.


3.1

The reduction argument

Our reduction argument is primarily based on partitioning the number of
triangulations of some convex graph G into those which include a specific
span-2 edge ei and those which do not (assuming there is at least one span2 edge in G). Let us already point out the tree structure implied by the
partitioning.
v0
v7
v1

e0
e1

e7
v6

v0

K8

e6

e2

v7

v0

v2

v7

v1

v1

e5

e3
e4

v5

v6

K7

v3

v2

v6

K8,−1

v2

v4
v5

v5
v3

v3

v4

v4

Figure 3: Reduction for the complete Kn , working on v0 /e0
Proposition 5 Let G = (V, E) be a convex geometric graph and T (G) the
number of its triangulations. Then, for any span-2 edge ei we have that
T(G | ei included) = T(G \ vi ).
Obviously, the following holds: T (G) = T (G \ vi ) + T (G \ ei ).
Proof. Observe that if ei is selected to participate in a triangulation TC ,
then all edges incident to vi may not participate in TC , as they all cross
ei . Therefore, the number of triangulations where ei is included is exactly
determined by the number of triangulations of G \ vi , as adding the “hat”
9

vi−1 vi vi+1 in any of the latest will yield a distinct triangulation of the original
graph.

Figure 3 demonstrates the above, nevertheless for the special case of an
initial complete graph. However, we easily get that T (Kn,0 ) = T (Kn−1,0 ) +
T (Kn,−1 ), which is essentially the first of the BC relations.
Now, consider a Kn,−1 graph. If we work on v1 /e1 (Figure 4, marked
blue vertex), thus the selection or not of e1 for the next branching of our
tree, we obtain either a K7 ≡ K7,0 (left child), either a K8,−2 . In general
(Figure 5), working on the next available span-2 edge, we reduce Kn,−m is
to either a Kn−1,−m+1 (left child) or a Kn,−m−1 (right child).
v0
v7
v1

v6

v0

v0

K8,−1

v2

v7

v7

v1

v1

v5

v6

v3

K7

v6

K8,−2

v2

v2

v4
v5

v5
v3

v3

v4

v4

Figure 4: Reduction for Kn,−1 , working on the next vertex/span-2 edge
It proves that the key to our reduction is the correct definition of the
next vertex (or span-2 edge) to work on. If, for instance, while on K8,−1
we select to work on v5 /e5 , the nice to our reduction K7 does not pop out.
More importantly, we would miss the recurring of isomorphic graphs, which
give us the number of triangulations they feature per class (Kn,−m ), and not
per specific instance.
Definition 1 (Next vertex/span-2 edge) Given a properly labeled convex geometric graph on n vertices, missing only m consecutive span-2 edges,
ei , ei+1 , ..., ei+m . The next vertex/span-2 edge is the pair vm+1 /em+1 .
Now, let us formally prove our claim.
Theorem 6 For any Kn,−m and −n + 1 ≤ −m ≤ −1, it is
T (Kn,−m ) = T (Kn−1,−m+1 ) + T (Kn,−m−1 )
10

v0
v7
v1

v6

v 0 ≡ r0
v 7 ≡ r6

v0

K8,−3

v2

v1

v5
v 6 ≡ r5

v7

v 1 ≡ r1

v3

K7,−2

v6

K8,−4

v 2 ≡ r2

v2

v4
v 5 ≡ r4

v5

v3

v3

v 4 ≡ r3

v4

Figure 5: Reduction for Kn,−m , working on the next vertex/span-2 edge
Also, it is
T (Kn,−m ) = an−2,m
for all defined quantities.
Proof. Without loss of generality (see 9), we may relabel our initial graph
–if necessary– and have the edges e0 , ..., em−1 as the missing span-2 ones.
The next vertex/span-2 edge is the pair vm /em . The right subtree is rooted
to a Kn,−m−1 graph, as it derives from deleting em , having a consecutive
m + 1 span-2 (but no other) edges missing.
For the left subtree, deleting vm leaves us to examine the edges of a
graph on n − 1 vertices. We have that edges vn−1 v1 , v0 v2 , ..., vm−3 vm−1
are all missing from the induced subgraph, and together they add up to
m − 1 consecutive span-2 edges. Edge vm−2 vm , missing from Kn,−m is not a
potential edge of the smaller graph. Edge vm−1 vm+1 has now become a side
of the (n − 1)-gon, and vm−2 vm+1 and vm−1 vm+2 are now span-2 edges of
the new graph, as are all the (potentially) remaining vm+1 vm+3 , ..., vn−2 v0 .
Thus, we have obtained a Kn−1,−m+1 graph. To complete the proof, we
remind that:
• Proposition 4 gives us T (Kn,−n+2 ) = 0 for pentagons and up; but
T (K4,−2 ) gives the number of triangulations of a quadrilateral missing
all 2 span-2 edges, therefore the relation is satisfied for all n ≥ 4.
• T (K3,0 ) = 1, as K3 is a triangle.
11

• K3,−1 and K2,0 are not properly defined as convex graphs, and not
actually needed, but for sake of completeness, we shall consider their
number of triangulations equal to a1,1 and a0,0 respectively.

Theorem 7 Our main sampling algorithm scheme adopted for convex triangulations yields an algorithm of running time O(n2 ).
Proof. As an outline, the quadratic (and not linear) time is due to the
information that must be stored when branching left. For a complete proof,
refer to the Appendix. Yet, we note that [8] implies a linear algorithm by
sampling monotone lattice paths, first. However, if one wants to preserve
one-to-one relation between the subinstances of the two problems, we are
not aware of any work proposing any similar framework to ours.


4

Mountain ranges

The mountain range problem consider the ways to form a “mountain range”
with n upstrokes and n downstrokes that all stay above a horizontal line. As
with the convex triangulations, we assume the space of all solutions, that is
actually a n×n lattice rotated as to comprehend our node to node movement
as Up or Down and always maintaining direction to the right (w.l.o.g.).
Assume we are on the horizon, or level 0, so we have to move Up. Our
actual choice is whether to go further Up or slant Down. The latest case
brings us to the horizon with 1 upstroke and downstroke to our left, therefore
the remaining mountain ranges are exactly the mountain ranges with n − 1
upstrokes and downstrokes - correlate to the left child of the BC-implied
tree. That is:
rn,0 = rn−1,0 + rn,1
where the remainder rn,1 denotes the case we moved Up. Of course, the
cases yield mutually disjoint mountain ranges.
It is easy enough to go on, explaining that if we are not on the horizon
(m ≥ 1), we are not dictated to move up (unless we cannot - the “height” or
the range is at most n). If we move up, our m increases by one. If we move
down, we “see” again a disjoint set of potential solutions. Since we slanted
down (m decreased) we can symbolize this reduction by
rn,m = rn−1,m−1 + rn,m+1
.
Theorem 8 The main algorithm obtained by our scheme for the mountain
ranges problem is linear.
12

Proof. We need linear in n coin tosses to get the code of the mountain
range; we branch linear in n times and for each node we lie on, we store a
linear amount of information (Ups-Downs) to backtrack to the root.


A

Omitted proofs

Proof. [Proof of Theorem 1] We will consider the 2 main of the BC-relations.
The marginal cases are trivial to prove.
an,0 = an−1,0 + an,1

⇔

Nn,n−1 = Nn−1,n−2 + Nn,n−2





1
2n
2n − 2
2n − 1
1
3
=
+
n n−1
n−1 n−2
2n − 1 n − 2


(2n − 2)!
3(2n − 2)!
(2n)!
=
+
n!(n + 1)!
(n − 1)!n! (n − 2)!(n + 1)!

(2n − 1)(2n)
1
3
=
+
(n + 1)!
(n − 1)! (n − 2)!(n + 1)

2(2n − 1)
1
3
=
+
(n − 1)(n + 1)
(n − 1) (n + 1)

⇔
⇔
⇔
⇔
⇔

4n − 2 = (n + 1) + 3(n − 1),

which holds.

Regarding an,m = an−1,m−1 + an,m+1 we have:
Nn,m = Nn−1,m + Nn,m−1





n−m n+m
n−m+2 n+m
n+1−m n+1+m
=
+
n+1+m
n+m
n+m
m
m
m−1


(n + 1 − m)(n + m)!
(n − m)(n + m)!
(n − m + 2)(n + m)!
=
+
m!(n + 1)!
(n + m)m!n!
(n + m)(m − 1)!(n + 1)!
(n − m)
(n − m + 2)
(n + 1 − m)
=
+
m(n + 1)
(n + m)m (n + m)(n + 1)

1
1
1
2
(n − m + 2)
−
=
−
+
m n+1
m n + m (n + m)(n + 1)
2
1
(n − m + 2)
−
=
n+m n+1
(n + m)(n + 1)
2(n + 1) − (n + m) = n − m + 2,

⇔
⇔
⇔
⇔
⇔
⇔

which holds.

Therefore, we have completed our proof.

Proof. [Proof of Theorem 2] Let G be the generating function for the numbers

13

ai,j , i.e.
G(x, y) =

∞
∞ X
X

ai,j xi y j

i=0 j=0

and let B be the generating function for numbers bi,j = ai+1,j for all i, j ≥ 0.
We will first determine B, and then it is simply:
G = xB + 1.

(8)

Initially, let us break B into sums of fixed j:
B = A0 + A1 + A2 + ... =

∞
X

Ak ,

(9)

k=0

where for all k ∈ N Ak =

P∞

i=0 bi,k x

A0 =

iyk .

From the BC-relation 4 we obtain:

1
A1 + xA0 + 1,
y

(10)

while from the recursive BC-relation 5 we obtain:
∀k > 0 Ak =

1
Ak+1 + xyAk−1 .
y

(11)

We have also showed that the numbers ai,0 are actually Catalan numbers,
in particular bi,0 = ai+1,0 = Ci+1 , for i ≥ 0. So, if Cat is the generating
function of the Catalan numbers, then:
Cat = xA0 + 1 ⇒ A0 =

Cat − 1
.
x

(12)

It is well known that:
Cat(x) =

1−

√

1 − 4x
.
2x

(13)

In order to get the generating function G, plug equations 10,11,12,13 into
equation 9:
1
(A1 + A2 + ...) + xy(A0 + A1 + A2 + ...) + xA0 + 1
y
1
= (G − A0 ) + xyG + xA0 + 1
y

B=

Cat(x)−1

y + (xy − 1)
y + (xy − 1)A0
x
=
2
y − 1 − xy
y − 1 − xy 2
√
y
(xy − 1)(1 − 1 − 4x − 2x)
=
+
.
y − 1 − xy 2
2x2 (y − 1 − xy 2 )
=

14

Finally, from relation 8 he have:
√
(1 − xy)(1 − 1 − 4x − 2xy)
G(x, y) = xB(x, y) + 1 =
.
2x(1 − y + xy 2 )

Observe that we did not directly use the initial condition that an,n =
0, n ≥ 1; we actually did account for it, as it is hidden in the proof that the
numbers an,0 correspond to Catalan numbers.

B

Notes on the main sampling algorithm for convex triangulations

For our convenience, we hereby adopt the notation Tn,−m = T (Kn,−m ).
The left child of a Kn,−m in our reduction is a graph on n − 1 vertices,
in other words, w.r.t. our initial proper vertex labeling, the labeling of the
left child is not proper, as a vertex is missing. Therefore, we must relabel
this graph, and every left child graph of the tree. The following Rule gives
the final ingredient for building the desirable reduction tree.
Rule 9 Let Kr,−m be the left child of a node of a tree rooted at Kn . If
m = 0, then relabel the complete Kr as desired. Else, place r0 opposite to
the first missing span-2 edge and complete with a proper relabeling. For each
new graph, maintain a 1 × n table to indicate the mapping of the current
to the initial labeling; current missing vertices of the parent graph can be
marked (e.g. −1 entries).
B.0.1

Properties of the reduction tree

In all, we have build a triangulation tree with the following properties:
• Every node has 2 children (left and right – binary tree).
• Every node indicating Kr,−m needs O(n) time to be created and coded:
store integers r and m, the 1×n mapping matrix for the vertex labeling,
plus a 2 integer indicator for backtracking to the parent node: if it is a
left child, hold [vm , −1], for a right child hold [vm−1 , vm+1 ] where vm is
the critical vertex of the parent node w.r.t. which the node branched
(store as labeled in the parent node).
• For any node, the triangulations coded in the left subtree are disjoint
to the ones of the right subtree, as they differ at the edge w.r.t. which
the node branched.
• If a node is K3 , then stop and mark one triangulation (green leaf).
Due to the above, all green leaves are left children and there is a total
of exactly Cn−2 green leaves in the tree.
15

• If a node is of the form Kr,−r+2 , then stop and mark no triangulation
(red leaf)
• Considering all the above, from any green leaf, backtracking to the root
is equivalent to obtaining one specific triangulation; this is achieved in
O(n) time.
0
4

\v

1

3

\e

2

0

0
4

1

3

4

2

3

0

0

4

1

3

2

0

4

2

1

1

3

0

4

2

1

3

4

2

1

3

2

T1
0

0

4

1

3

2

T2

0

4

1

3

2

4

1

3

4

2

0

0

0
1

3

4

2

4

1

3

1

3

2

2

T3
0

0

4

1

3

2

T4

0

4

1

3

2

0

4

1

3

2

4

1

3

T5

Figure 6: Full reduction tree for the convex pentagon. Blue color indicates
the working on node. Relabelings are not marked. Each of its 5 triangulations is encoded in a different green leaf.
Figure 6 shows the full reduction tree for the convex K5 . To give a for
instance, consider the green leaf encoding triangulation T3 . T3 includes the
triangle v0 v3 v4 (end of reduction); as a left child of its parent node, which
branched w.r.t. v2 /v0 v3 , it includes v0 v3 as an span-2 edge of the parent K4
subgraph, so triangle v0 v2 v3 is in T4 . The K4 parent node is a left child of
the K5,−1 node which branched w.r.t. v1 , therefore the triangulation does
also include triangle v0 v1 v2 ; finally (though not necessary), the K5,−1 node
being a right child of the K5 which branched w.r.t. v0 suggests that v4 v1 is
missing from the T4 .
Note that this is a small example, and some leaves (T2 , T4 , T5 ) already
16

2

indicate unambiguously the encoded triangulation. Observe also that even
if it is not directly visible that T1 differs from T4 , our simple branching
rule guarantees that T1 includes v4 v1 as an edge, while T4 does not, as they
belong to a different subtree of the root node which branched w.r.t. v0 /v4 v1 .

References
[1] Victor Alvarez, Karl Bringmann, Saurabh Ray, and Raimund Seidel. Counting triangulations and other crossing-free structures approximately. Comput. Geom., 48(5):386–397, 2015.
[2] Victor Alvarez and Raimund Seidel. A simple aggregative algorithm
for counting triangulations of planar point sets and related problems.
In Symposuim on Computational Geometry 2013, SoCG ’13, Rio de
Janeiro, Brazil, June 17-20, 2013, pages 1–8, 2013.
[3] J. Ambjorn, B. Durhus, and T. Jonsson. Quantum Geometry: A Statistical Field Theory Approach. Cambridge Monographs on Mathematical
Physics, Cambridge University Press, Cambridge, 1997.
[4] Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis, Petros Pantavos, and
Stathis Zachos. Completeness results for counting problems with easy
decision. In Algorithms and Complexity - 10th International Conference,
CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, pages 55–
66, 2017.
[5] Prosenjit Bose, Ferran Hurtado, Eduardo Rivera-Campo, and David R.
Wood. Partitions of complete geometric graphs into plane trees. Comput. Geom., 34(2):116–125, 2006.
[6] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H.
Overmars. Computational geometry: algorithms and applications, 3rd
Edition. Springer, 2008.
[7] 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, Kingston, Ontario, Canada, August 1114, 1997, 1997.
[8] Luc Devroye, Philippe Flajolet, Ferran Hurtado, Marc Noy, and
William L. Steiger. Properties of random triangulations and trees. Discrete & Computational Geometry, 22(1):105–117, 1999.
[9] Q. Ding, J. Qian, W. Tsang, and C. Wang. Randomly generating triangulations of a simple polygon. In Computing and Combinatorics, 11th
Annual International Conference, COCOON 2005, Kunming, China,
August 16-29, 2005, Proceedings, pages 471–480, 2005.
17

[10] Peter Epstein, J. Kavanagh, A. Knight, J. May, T. Nguyen, and JörgRüdiger Sack. A workbench for computational geometry. Algorithmica,
11(4):404–428, 1994.
[11] Peter Epstein and Jörg-Rüdiger Sack. Generating triangulations at random. ACM Trans. Model. Comput. Simul., 4(3):267–278, 1994.
[12] W. Feller. An introduction to probability theory and its applications.
Number v. 1. Wiley, 1968.
[13] Leonidas J. Guibas and John Hershberger. Optimal shortest path
queries in a simple polygon. J. Comput. Syst. Sci., 39(2):126–152, 1989.
[14] Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, and
Robert Endre Tarjan. Linear-time algorithms for visibility and shortest
path problems inside triangulated simple polygons. Algorithmica, 2:209–
233, 1987.
[15] Ferran Hurtado and Marc Noy. Ears of triangulations and catalan numbers. Discrete Mathematics, 149(1-3):319–324, 1996.
[16] Ferran Hurtado and Marc Noy. Graph of triangulations of a convex polygon and tree of triangulations. Comput. Geom., 13(3):179–188, 1999.
[17] Donald E. Knuth. Estimating the efficiency of backtrack programs.
Technical report, Stanford, CA, USA, 1974.
[18] D. T. Lee. Visibility of a simple polygon. Computer Vision, Graphics,
and Image Processing, 22(2):207–221, 1983.
[19] Lisa McShine and Prasad Tetali. On the mixing time of the triangulation walk and other catalan structures. In Randomization Methods
in Algorithm Design, Proceedings of a DIMACS Workshop, Princeton,
New Jersey, USA, December 12-14, 1997, pages 147–160, 1997.
[20] Michael S. O. Molloy, Bruce A. Reed, and William Steiger. On the mixing rate of the triangulation walk. In Randomization Methods in Algorithm Design, Proceedings of a DIMACS Workshop, Princeton, New
Jersey, USA, December 12-14, 1997, pages 179–190, 1997.
[21] Takao Nishizeki and Md. Saidur Rahman. Planar Graph Drawing, volume 12 of Lecture Notes Series on Computing. World Scientific, 2004.
[22] Joseph O’Rourke. Computational Geometry in C. Cambridge University
Press, New York, NY, USA, 2nd edition, 1998.
[23] Mohammad Tanvir Parvez, Md. Saidur Rahman, and Shin-Ichi Nakano.
Generating all triangulations of plane graphs. J. Graph Algorithms
Appl., 15(3):457–482, 2011.
18

[24] Dominique Poulalhon and Gilles Schaeffer. Optimal coding and sampling of triangulations. Algorithmica, 46(3-4):505–527, 2006.
[25] Sadiq M. Sait and Habib Youssef. VLSI Physical Design Automation Theory and Practice, volume 6 of Lecture Notes Series on Computing.
World Scientific, 1999.
[26] Micha Sharir and Adam Sheffer. Counting triangulations of planar point
sets. Electr. J. Comb., 18(1), 2011.
[27] Micha Sharir, Adam Sheffer, and Emo Welzl. On degrees in random
triangulations of point sets. J. Comb. Theory, Ser. A, 118(7):1979–1999,
2011.
[28] Micha Sharir and Emo Welzl. Random triangulations of planar point
sets. In Proceedings of the 22nd ACM Symposium on Computational
Geometry, Sedona, Arizona, USA, June 5-7, 2006, pages 273–281, 2006.
[29] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Inf. Comput., 82(1):93–133,
1989.
[30] Richard P. Stanley. Catalan Numbers. Cambridge University Press,
2015. doi:10.1017/CBO9781139871495.
[31] Robert Endre Tarjan and Christopher J. Van Wyk. An o(n log log n)time algorithm for triangulating a simple polygon. SIAM J. Comput.,
17(1):143–178, 1988.

19

