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 πn,λ under which each partial triangulation σ is assigned probability proportional to λ|σ|, where λ>0 is a model parameter and |σ| ∈ {0,…,n−1} denotes the number of diagonals in σ. 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 πn,λ with expected running time O((min{n,n√λ}+1)log n), which is optimal up to the logarithmic factor.
Related
- The Pólya--Szegő conjecture for convex polygons with many sides
- A Combinatorial Benders Decomposition Framework for Two-Dimensional Irregular Bin Packing Problems with Convex Polygons
- The fence conjecture for convex projective polygons
- Convex-cyclic and super convex-cyclic weighted shifts
- Continuity and monotonicity of weighted perimeters of convex bodies
BibTeX
@misc{blanca2026weighted,
title = {{On weighted partial triangulations of convex polygons}},
author = {Antonio Blanca and Alexandre Stauffer and Izabella Stuhl},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.21921},
eprint = {2605.21921},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.21921},
}
RIS
TY - UNPB
TI - On weighted partial triangulations of convex polygons
AU - Antonio Blanca
AU - Alexandre Stauffer
AU - Izabella Stuhl
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2605.21921
UR - https://arxiv.org/abs/2605.21921
AB - We study the problem of sampling weighted partial triangulations of a convex polygon with n+2 sides. We consider the distribution π_n,λ under which each partial triangulation σ is assigned probability proportional to λ^|σ|, where λ>0 is a model parameter and |σ| ∈ {0,…,n−1} denotes the number of diagonals in σ. 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 π_n,λ with expected running time O((min{n,n√λ}+1)log n), which is optimal up to the logarithmic factor.
ER -