Skip to main content
Full-text links:


Current browse context:

new | recent | 1911

Change to browse by:

References & Citations


BibSonomy logo Mendeley logo Reddit logo ScienceWISE logo

Mathematics > Probability

Title:Minimum weight disk triangulations and fillings

Abstract: We study the minimum total weight of a disk triangulation using vertices out of $\{1,\ldots,n\}$, where the boundary is the triangle $(123)$ and the $\binom{n}3$ triangles have independent weights, e.g. $\mathrm{Exp}(1)$ or $\mathrm{U}(0,1)$.
We show that for explicit constants $c_1,c_2>0$, this minimum is $c_1 \frac{\log n}{\sqrt n} + c_2 \frac{\log\log n}{\sqrt n} + \frac{Y_n}{\sqrt n}$ where the random variable $Y_n$ is tight, and it is attained by a triangulation that consists of $\frac14\log n + O_P(\sqrt{\log n}) $ vertices.
Moreover, for disk triangulations that are canonical, in that no inner triangle contains all but $O(1)$ of the vertices, the minimum weight has the above form with the law of $Y_n$ converging weakly to a shifted~Gumbel. In addition, we prove that, with high probability, the minimum weights of a homological filling and a homotopical filling of the cycle $(123)$ are both attained by the minimum weight disk triangulation.
Comments: 16 pages, 2 figures
Subjects: Probability (math.PR); Combinatorics (math.CO)
MSC classes: 60C05, 57M20
Cite as: arXiv:1911.02569 [math.PR]
  (or arXiv:1911.02569v1 [math.PR] for this version)

Submission history

From: Eyal Lubetzky [view email]
[v1] Wed, 6 Nov 2019 19:00:00 UTC (25 KB)