Random polytope

In mathematics, a random polytope is a structure commonly used in convex analysis and the analysis of linear programs in d-dimensional Euclidean space ${ℝ}^d$. Depending on use the construction and definition, random polytopes may differ.

Random polytope of a set of random points in accordance with definition 1

Definition

There are multiple non equivalent definitions of a Random polytope. For the following definitions. Let K be a bounded convex set in a Euclidean space:

• The convex hull of random points selected with respect to a uniform distribution inside K.
• The nonempty intersection of half-spaces in ${ℝ}^d$.
  • The following parameterization has been used: $r:({ℝ}^d\times \{0,1\}{)}^m\to \text{Polytopes}\in {ℝ}^d$ such that $r((p_1,0),(p_2,1),(p_3,1)...(p_m,i_m))=\{x\in {ℝ}^n:|\frac{p_j}{||p_j||}\cdot x\le ||p_j||\text{ if }{i}_j=1,\frac{p_j}{||p_j||}\cdot x\ge ||p_j||\text{ if }{i}_j=0\}$ (Note: these polytopes can be empty).

Properties definition 1

Let $\mathrm{K}$ be the set of convex bodies in ${ℝ}^d$. Assume $K\in \mathrm{K}$ and consider a set of uniformly distributed points $x_1,...,x_n$ in $K$. The convex hull of these points, $K_n$, is called a random polytope inscribed in $K$. $K_n=[x_1,...,x_n]$ where the set $[S]$ stands for the convex hull of the set. We define $E(k,n)$ to be the expected volume of $K-K_n$. For a large enough $n$ and given $K\in {ℝ}^n$.

• vol $K(\frac{1}{n})\ll E(K,n)\ll$ vol $K(\frac{1}{n})$
  • Note: One can determine the volume of the wet part to obtain the order of the magnitude of $E(K,n)$, instead of determining $E(K,n)$.
• For the unit ball $B^d\in {ℝ}^d$, the wet part $B^d(v\le t)$ is the annulus $\frac{B^d}{(1-h)B^d}$ where h is of order $t^{\frac{2}{d+1}}$: $E(B^d,n)\approx$ vol $B^d(\frac{1}{n})\approx n^{\frac{-2}{d+1}}$

Given we have $V=V(x_1,...,x_d)$ is the volume of a smaller cap cut off from $K$ by aff$(x_1,...,x_d)$, and $F=[x_1,...,x_d]$ is a facet if and only if $x_{d+1},...,x_n$ are all on one side of aff $\{x_1,...,x_d\}$.

• $E_{\varphi }(K_n)=(\genfrac{}{}{0ex}{}{n}{d})\underset{K}{\int }...\underset{K}{\int }[(1-V{)}^{n-d}+V^{n-d}]\varphi (F)d{x}_1...d{x}_d$.
  • Note: If $\varphi =f_{d-1}$ (a function that returns the amount of d-1 dimensional faces), then $\varphi (F)=1$ and formula can be evaluated for smooth convex sets and for polygons in the plane.

Properties definition 2

Assume we are given a multivariate probability distribution on $({ℝ}^d\times \{0,1\}{)}^m=(p_1\times i_1,\dots ,p_m\times i_m{)}^m$ that is

1. Absolutely continuous on $(p_1,\dots ,p_d)$ with respect to Lebesgue measure.
2. Generates either 0 or 1 for the $i$s with probability of $\frac{1}{2}$ each.
3. Assigns a measure of 0 to the set of elements in $({ℝ}^d\times \{0,1\}{)}^m$ that correspond to empty polytopes.

Given this distribution, and our assumptions, the following properties hold:

• A formula is derived for the expected number of $k$ dimensional faces on a polytope in ${ℝ}^d$ with $m$ constraints: $E_k(m)=2^{d-k}\sum _{i=d-k}^d(\genfrac{}{}{0ex}{}{i}{d-k})(\genfrac{}{}{0ex}{}{m}{i})/\sum _{i=0}^d(\genfrac{}{}{0ex}{}{m}{i})$. (Note: $\underset{m\to \mathrm{\infty }}{\lim }{E}_k(m)=(\genfrac{}{}{0ex}{}{d}{d-k})2^{d-k}$ where $m>d$). The upper bound, or worst case, for the number of vertices with $m$ constraints is much larger: $V_{max}=(\genfrac{}{}{0ex}{}{m-[\frac{1}{2}(d+1)]}{m-d})+(\genfrac{}{}{0ex}{}{m-[\frac{1}{2}(d+2)]}{m-d})$.
• The probability that a new constraint is redundant is: ${\pi }_m=1-\frac{2\sum _{i=0}^{d-1}(\genfrac{}{}{0ex}{}{m-1}{i})}{\sum _{i=0}^d(\genfrac{}{}{0ex}{}{m}{i})}$. (Note: $\underset{m\to \mathrm{\infty }}{\lim }{\pi }_m=1$, and as we add more constraints, the probability a new constraint is redundant approaches 100%).
• The expected number of non-redundant constraints is: $C_d(m)=\frac{2m\sum _{i=0}^{d-1}(\genfrac{}{}{0ex}{}{m-1}{i})}{\sum _{i=0}^d(\genfrac{}{}{0ex}{}{m}{i})}$. (Note: $\underset{m\to \mathrm{\infty }}{\lim }{C}_d(m)=2d$).

Example uses

• Minimal caps
• Macbeath regions
• Approximations (approximations of convex bodies see properties of definition 1)
• Economic cap covering theorem (see relation from properties of definition 1 to floating bodies)