| Properties of random triangulations and trees (1999) | |||||||||||||||
Abstract | |||||||||||||||
| 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 non-negative lattice paths that start at 0, make 2n−4stepsXi 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 behaviour 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 uniformly generate triangulations in Tn, and in certain interesting subsets. (KEYWORDS: triangulation, random binary tree, probabilistic analysis, computational geometry) 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||