Convex polytope

A convex polytope is a bounded intersection of finitely many closed half-spaces, equivalently the convex hull of finitely many points.

A zonotope is a Minkowski sum of finitely many line segments, equivalently an affine map image of a cube. For vectors ${\xi }_j$, the set ${\sum }_j[0,1]{\xi }_j$ is the support of the associated box spline. A centred version uses $[-1/2,1/2]{\xi }_j$ instead. In two dimensions, sums of differently directed segments give centrally symmetric polygons; repeated directions lengthen their corresponding edges without adding new edge directions.

A lattice polytope is the convex hull of finitely many points of a Euclidean lattice. It need not contain the origin. Integral translation changes its associated homogeneous semigroup ring by a grading-preserving isomorphism.

// Target: geometry-and-topology.bigb

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 strictly convex polygon is a convex polygon whose interior angles are all strictly less than $180$ degrees.

For a finite point set in the plane, a convex polygon whose vertices of a polygon belong to the set and whose interior contains no point of the set. The convention must specify whether additional points on the boundary are allowed. A fan triangulation reduces emptiness to tests on constituent triangles, together with checks that internal diagonals contain no forbidden points.

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.

A vertex of a convex polytope is an extreme point: it cannot be expressed as a nontrivial convex combination of two distinct points in that polytope. In a full-dimensional simple polytope of dimension $n$, a vertex lies on exactly $n$ incident facets.

A facet of a full-dimensional convex polytope in ${\mathbb{R}}^n$ is a face of dimension $n-1$. Each irredundant supporting closed half-space defines one facet.

If $r\ge \sqrt{2}$ and a convex polytope satisfies $r^{-1}{B}^n\subseteq P\subseteq B^n$, then it has at least $(1-r^{-2}{)}^{-n/2}\ge e^{n/(2r^2)}$ facets. Its outward facet normals define spherical caps covering the unit sphere; the spherical cap area upper bound supplies the estimate.

The convex hull of the positive and negative coordinate unit vectors. Its boundary triangulates a sphere, and each face contains at most one member of each antipodal pair of coordinate unit vectors. This makes its barycentric subdivision useful for triangulating Real projective space.