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 $\mathbb {R} ^{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 $\mathbb {R} ^{d}$.
  • The following parameterization has been used: $r:(\mathbb {R} ^{d}\times \{0,1\})^{m}\rightarrow {\text{Polytopes}}\in \mathbb {R} ^{d}$ such that $r((p_{1},0),(p_{2},1),(p_{3},1)...(p_{m},i_{m}))=\{x\in \mathbb {R} ^{n}:|{\frac {p_{j}}{||p_{j}||}}\cdot x\leq ||p_{j}||{\text{ if }}i_{j}=1,{\frac {p_{j}}{||p_{j}||}}\cdot x\geq ||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 $\mathbb {R} ^{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 \mathbb {R} ^{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 \mathbb {R} ^{d}$, the wet part $B^{d}(v\leq 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_{\phi }(K_{n})={{n} \choose {d}}\int _{K}...\int _{K}[(1-V)^{n-d}+V^{n-d}]\phi (F)dx_{1}...dx_{d}$.
  • Note: If $\phi =f_{d-1}$ (a function that returns the amount of d-1 dimensional faces), then $\phi (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 $(\mathbb {R} ^{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 $(\mathbb {R} ^{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 $\mathbb {R} ^{d}$ with $m$ constraints: $E_{k}(m)=2^{d-k}\sum _{i=d-k}^{d}{{i} \choose {d-k}}{{m} \choose {i}}/\sum _{i=0}^{d}{{m} \choose {i}}$. (Note: $\lim _{m\to \infty }E_{k}(m)={{d} \choose {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}={m-[{\frac {1}{2}}(d+1)] \choose m-d}+{m-[{\frac {1}{2}}(d+2)] \choose m-d}$.
• The probability that a new constraint is redundant is: $\pi _{m}=1-{\frac {2\sum _{i=0}^{d-1}{{m-1} \choose i}}{\sum _{i=0}^{d}{m \choose i}}}$. (Note: $\lim _{m\to \infty }{\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}{{m-1} \choose i}}{\sum _{i=0}^{d}{{m} \choose i}}}$. (Note: $\lim _{m\to \infty }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)