Convex polygon

A convex polygon is a two-dimensional convex polytope, equivalently the convex hull of a finite planar set with nonempty interior. Its vertices are the extreme points of that hull. Saying that given points form a convex polygon means every specified point is a vertex; points inside the hull or in the interior of a straight boundary segment do not count as vertices.

A triangulation of a convex polygon divides a convex polygon into triangles using diagonals between its existing vertices of a polytope, with no diagonal crossings in the interior. For $m\ge 3$ vertices it uses $m-3$ diagonals and produces $m-2$ triangles. Fixing one boundary edge, its adjacent triangle separates two smaller polygon regions; summing over the possible third vertices of a polytope gives the Catalan recurrence. Thus the number of triangulations of a convex polygon is $C_{m-2}$, with $C_n$ the Catalan number. A quadrilateral has two choices and a pentagon has five.

A convex chain between two fixed points inside a triangle is a finite point set whose union with the endpoints forms the vertices of a convex polygon, with the endpoint segment as one boundary edge. In the triangle $0\le y\le x\le 1$, with endpoints $(0,0)$ and $(1,1)$, its ordered lower boundary has strictly increasing segment slopes. Every subset of its intermediate vertices remains a convex chain. This hereditary property lets selected point coordinates certify the existence of a long chain.

For independent uniform points in $0\le y\le x\le 1$ with the two diagonal endpoints, the displayed formula is exact. Order the $k$ intermediate points so that both coordinates increase, and write the $k+1$ positive coordinate spacings as $(u_i)$ and $(v_i)$, with each sum equal to one. The two spacing vectors have uniform simplex measure, independently, and the full ordered-coordinate region has volume $1/(k!{)}^2$. Simultaneous permutation of the spacing pairs preserves that measure, so all $(k+1)!$ orders of the ratios $v_i/u_i$ have equal volume. Strictly increasing ratios characterize a convex chain and automatically place the intermediate points below the diagonal. Thus its ordered volume is $1/((k!{)}^2(k+1)!)$. There are $k!$ ways to assign labels, and uniform triangle density is $2^k$, giving the formula. Consequently the first moment method bounds the probability of any length-$k$ chain among $n$ points by $\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k/(k!(k+1)!)$.

For $n$ points in a triangle and two fixed endpoint vertices, the longest convex chain length is the largest number of sampled points in a convex chain joining those endpoints. It is a certifiable function: a chain of length $a$ supplies a certificate of exactly $a$ point coordinates. Changing one point changes the maximum by at most one, since deleting that point from any optimal chain loses at most one vertex. For independent uniform points, its median is $O(n^{1/3})$ and its fluctuation scale about the median is at most $n^{1/6}$, as proved by convex-chain probability in a triangle and convex-chain median concentration.

Let $m$ be an integer median for the longest convex chain length of independent uniform points in a triangle. If $L_n(x)\ge a$, fix a certificate of $a$ coordinates. Every configuration with $L_n\le b$ must disagree with at least $a-b$ of those coordinates; equal weights $1/\sqrt{a}$ prove Talagrand convex distance separation at least $(a-b)/\sqrt{a}$. Talagrand's convex distance inequality then gives $\mathbb{P}(L_n\ge a)\mathbb{P}(L_n\le b)\le e^{-(a-b{)}^2/(4a)}$. Set $b=m$, then $a=m$, in the two respective applications to obtain the displayed tails for positive integer $t$. The exact chain-counting bound gives $m\le C{n}^{1/3}$. Hence any interval centred at $m$ with length $\omega (n)n^{1/6}$, where $\omega (n)\to \infty$, contains $L_n$ with high probability. No upper restriction on the growth of $\omega$ is required.