On weighted partial triangulations of convex polygons

Abstract

We study the problem of sampling weighted partial triangulations of a convex polygon with $n+2$ sides. We consider the distribution ${\pi }_{n,\lambda }$ under which each partial triangulation $\sigma$ is assigned probability proportional to ${\lambda }^{|\sigma |}$, where $\lambda >0$ is a model parameter and $|\sigma |\in \{0,\dots ,n-1\}$ denotes the number of diagonals in $\sigma$. This model belongs to a broad class of weighted geometric partition problems that include lattice triangulations and dyadic tilings, and is closely related to several classical combinatorial structures, including the full triangulations of a convex polygon and the associated Catalan structures. Our main result is a simple exact sampling algorithm for ${\pi }_{n,\lambda }$ with expected running time $O((\min \{n,n\sqrt{\lambda }\}+1)\log n)$, which is optimal up to the logarithmic factor.