Properties of random triangulations and trees

Let T_n denote the set of triangulations of a convex polygon K with n sides. We study functions that measure very natural "geometric" features of a triangulation τ ∈ T_n for example, Δ_n (τ) which counts the maximal number of diagonals in τ incident to a single vertex of K. It is familiar that T_n is bijectively equivalent to B_n, the set of rooted binary trees with n - 2 internal nodes, and also to P_n, the set of nonnegative lattice paths that start at 0, make 2n - 4 steps X_i of size ±1, and end at X₁ + ⋯ + X_2n-4 = 0. Δ_n and the other functions translate into interesting properties of trees in B_n, and paths in P_n, that seem not to have been studied before. We treat these functions as random variables under the uniform probability on T_n and can describe their behavior quite precisely. A main result is that Δ_n is very close to log n (all logs are base 2). Finally we describe efficient algorithms to generate triangulations in T_n uniformly, and in certain interesting subsets.