= Longest convex chain
{title2=$L_n$}
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>.
Back to article page
