Misplaced Pages

This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (December 2022)

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

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 ${\displaystyle \mathbb {R} ^{d}}$.
  • The following parameterization has been used: ${\displaystyle r:(\mathbb {R} ^{d}\times \{0,1\})^{m}\rightarrow {\text{Polytopes}}\in \mathbb {R} ^{d}}$ such that ${\displaystyle 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 ${\displaystyle \mathrm {K} }$ be the set of convex bodies in ${\displaystyle \mathbb {R} ^{d}}$. Assume ${\displaystyle K\in \mathrm {K} }$ and consider a set of uniformly distributed points ${\displaystyle x_{1},...,x_{n}}$ in ${\displaystyle K}$. The convex hull of these points, ${\displaystyle K_{n}}$, is called a random polytope inscribed in ${\displaystyle K}$. ${\displaystyle K_{n}=}$ where the set ${\displaystyle }$ stands for the convex hull of the set. We define ${\displaystyle E(k,n)}$ to be the expected volume of ${\displaystyle K-K_{n}}$. For a large enough ${\displaystyle n}$ and given ${\displaystyle K\in \mathbb {R} ^{n}}$.

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

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

• ${\displaystyle E_{\phi }(K_{n})={{n} \choose {d}}\int _{K}...\int _{K}\phi (F)dx_{1}...dx_{d}}$.
  • Note: If ${\displaystyle \phi =f_{d-1}}$ (a function that returns the amount of d-1 dimensional faces), then ${\displaystyle \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 ${\displaystyle (\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 ${\displaystyle (p_{1},\dots ,p_{d})}$ with respect to Lebesgue measure.
2. Generates either 0 or 1 for the ${\displaystyle i}$s with probability of ${\displaystyle {\frac {1}{2}}}$ each.
3. Assigns a measure of 0 to the set of elements in ${\displaystyle (\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 ${\displaystyle k}$ dimensional faces on a polytope in ${\displaystyle \mathbb {R} ^{d}}$ with ${\displaystyle m}$ constraints: ${\displaystyle 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: ${\displaystyle \lim _{m\to \infty }E_{k}(m)={{d} \choose {d-k}}2^{d-k}}$ where ${\displaystyle m>d}$). The upper bound, or worst case, for the number of vertices with ${\displaystyle m}$ constraints is much larger: ${\displaystyle V_{max}={m- \choose m-d}+{m- \choose m-d}}$.
• The probability that a new constraint is redundant is: ${\displaystyle \pi _{m}=1-{\frac {2\sum _{i=0}^{d-1}{{m-1} \choose i}}{\sum _{i=0}^{d}{m \choose i}}}}$. (Note: ${\displaystyle \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: ${\displaystyle C_{d}(m)={\frac {2m\sum _{i=0}^{d-1}{{m-1} \choose i}}{\sum _{i=0}^{d}{{m} \choose i}}}}$. (Note: ${\displaystyle \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)

References

1. ^ May, Jerrold H.; Smith, Robert L. (December 1982). "Random polytopes: Their definition, generation and aggregate properties". Mathematical Programming. 24 (1): 39–54. doi:10.1007/BF01585093. hdl:2027.42/47911. S2CID 17838156.
2. ^ Baddeley, Adrian; Bárány, Imre; Schneider, Rolf; Weil, Wolfgang, eds. (2007), "Random Polytopes, Convex Bodies, and Approximation", Stochastic Geometry: Lectures given at the C.I.M.E. Summer School held in Martina Franca, Italy, September 13–18, 2004, Lecture Notes in Mathematics, vol. 1892, Berlin, Heidelberg: Springer, pp. 77–118, CiteSeerX 10.1.1.641.3187, doi:10.1007/978-3-540-38175-4_2, ISBN 978-3-540-38175-4, retrieved 2022-04-01
3. Bárány, I.; Larman, D. G. (December 1988). "Convex bodies, economic cap coverings, random polytopes". Mathematika. 35 (2): 274–291. doi:10.1112/S0025579300015266.

• Metric geometry
• Convex analysis
• Computational geometry