Jump to content

Random polytope

From Wikipedia, the free encyclopedia

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.

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

Definition

[edit]

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.[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

[edit]

Let 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

[edit]

Assume we are given a multivariate probability distribution on that is

  1. Absolutely continuous on with respect to Lebesgue measure.
  2. Generates either 0 or 1 for the s with probability of each.
  3. 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]
  1. ^ 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.
  2. ^ 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
  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.