Journal of Combinatorics

Volume 12 (2021)

Number 3

On typical triangulations of a convex $n$-gon

Pages: 389 – 412

DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n3.a2

Authors

Toufik Mansour (Department of Mathematics, University of Haifa, Israel)

Reza Rastegar (Departments of Mathematics and Engineering, University of Tulsa, Oklahoma, U.S.A.; and Occidental Petroleum Corporation, Houston, Texas, U.S.A.)

Abstract

Let $f_n$ be a function assigning weight to each possible triangle whose vertices are chosen from vertices of a convex polygon $P_n$ of $n$ sides. Suppose $\mathcal{T}_n$ is a random triangulation, sampled uniformly out of all possible triangulations of $n_.$ We study the sum of weights of triangles in $\mathcal{T}_n$ and give a general formula for average and variance of this random variable. In addition, we look at several interesting special cases of $f_n$ in which we obtain explicit forms of generating functions for the sum of the weights. For example, among other things, we give new proofs for already known results such as the degree of a fixed vertex and the number of ears in $\mathcal{T}_n$, as well as, provide new results on the number of “blue” angles and refined information on the distribution of angles at a fixed vertex. We note that our approach is systematic and can be applied to many other new examples while generalizing the existing results.

Keywords

convex polygon, random triangulation

2010 Mathematics Subject Classification

Primary 05A15, 52C05, 52C45. Secondary 05A19, 05C05.

Full Text (PDF format)

Received 27 March 2020

Accepted 26 August 2020

Published 8 November 2021