Let Tn 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 τ ∈ Tn for example, Δn (τ) which counts the maximal number of diagonals in τ incident to a single vertex of K. It is familiar that Tn is bijectively equivalent to Bn, the set of rooted binary trees with n - 2 internal nodes, and also to Pn, the set of nonnegative lattice paths that start at 0, make 2n - 4 steps Xi of size ±1, and end at X1 + ⋯ + X2n-4 = 0. Δn and the other functions translate into interesting properties of trees in Bn, and paths in Pn, that seem not to have been studied before. We treat these functions as random variables under the uniform probability on Tn 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 Tn uniformly, and in certain interesting subsets.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics