## Abstract

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_{1} + ⋯ + 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.

Original language | English (US) |
---|---|

Pages (from-to) | 105-117 |

Number of pages | 13 |

Journal | Discrete and Computational Geometry |

Volume | 22 |

Issue number | 1 |

DOIs | |

State | Published - Jul 1999 |

## All Science Journal Classification (ASJC) codes

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