On the Threshold for Triangulations Inside Convex Polygons

ABSTRACT Start with a large convex polygon and add all other edges inside independently with probability . At what critical threshold do triangulations of the polygon begin to appear? The first author and Gravner asked this question and observed that , using the relationship with the Catalan numbers and a coupling with oriented site percolation on . More recently, Archer, Hartarsky, the first author, Olesker‐Taylor, Schapira, and Valesin proved that , where is the Catalan exponential growth rate and is the critical threshold for oriented percolation. The upper bound is strict, but nonquantitative and follows by a renormalization argument. In this work, we show that using a simple ear clipping algorithm, which can be analyzed by comparing with random walks with negative drift. This bound is closer to the truth (perhaps near 0.4) and shows that most configurations of edges inside large convex polygons contain triangulations.