In mathematics, a random polytope is a structure commonly used in convex analysis and the analysis of linear programs in d-dimensional Euclidean space .[1][2] Depending on use the construction and definition, random polytopes may differ.
![](http://up.wiki.x.io/wikipedia/commons/thumb/3/36/RandomPoltyope%281%29.png/220px-RandomPoltyope%281%29.png)
Definition
editThere 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.[2]
- The nonempty intersection of half-spaces in .[1]
- The following parameterization has been used: such that (Note: these polytopes can be empty).[1]
Properties definition 1
editLet be the set of convex bodies in . Assume and consider a set of uniformly distributed points in . The convex hull of these points, , is called a random polytope inscribed in . where the set stands for the convex hull of the set.[2] We define to be the expected volume of . For a large enough and given .
- vol vol [2]
- Note: One can determine the volume of the wet part to obtain the order of the magnitude of , instead of determining .[3]
- For the unit ball , the wet part is the annulus where h is of order : vol [2]
Given we have is the volume of a smaller cap cut off from by aff , and is a facet if and only if are all on one side of aff .
- .[2]
- Note: If (a function that returns the amount of d-1 dimensional faces), then and formula can be evaluated for smooth convex sets and for polygons in the plane.
Properties definition 2
editAssume we are given a multivariate probability distribution on that is
- Absolutely continuous on with respect to Lebesgue measure.
- Generates either 0 or 1 for the s with probability of each.
- Assigns a measure of 0 to the set of elements in that correspond to empty polytopes.
Given this distribution, and our assumptions, the following properties hold:
- A formula is derived for the expected number of dimensional faces on a polytope in with constraints: . (Note: where ). The upper bound, or worst case, for the number of vertices with constraints is much larger: .[1]
- The probability that a new constraint is redundant is: . (Note: , and as we add more constraints, the probability a new constraint is redundant approaches 100%).[1]
- The expected number of non-redundant constraints is: . (Note: ).[1]
Example uses
edit- 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
edit- ^ a b c d e f 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.
- ^ a b c d e f 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
- ^ 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.