Properties of random triangulations and trees

L. Devroye, P. Flajolet, F. Hurtado, M. Noy, W. Steiger

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)105-117
Number of pages13
JournalDiscrete and Computational Geometry
Volume22
Issue number1
DOIs
StatePublished - Jul 1999

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Properties of random triangulations and trees'. Together they form a unique fingerprint.

Cite this