Jump to content

User:Bongilles/sandbox/Random convex hull

From Wikipedia, the free encyclopedia

Random convex hulls form one of the most classical models of random polytopes, along with typical and zero cells of random tessellations.

Historical example : Sylvester's Four-point problem

[edit]

In 1864 Sylvester posed the following question in the Educational time[1][2].

Show that the chance of four points forming the apices of a reentrant quadrilateral is 1/4 if they are taken in an indefinite plane...

With the modern eye of the probability theory it is clear that the problem is ill posed since the distribution of the points is not specified. Different assumptions lead to different answers. See[3] for more information.

Model

[edit]

They are build as the convex hull of a random discrete set of points in the Euclidean space . The set of points is typically a collection of i.i.d. points or a Poisson point process. On this page the following notation is used. For a probability measure on the convex hull of independent points distributed according to is denoted by For a measure on and real number the convex hull of a Poisson point process of intensity measure is denoted by In both of these cases the underlying measure is often the uniform distribution either inside a convex body or on its boundary, the normal distribution or more generally a log concave distribution.

The distribution of random polytopes are often studied through a number of their most common functionals such as the volume, number of faces or Hausdorff distance to a reference body. These functionals are described by statistics such as expectation and variance, asymptotic limit theorems (in most instances central limit theorem) or concentration bounds.

Probability that a point is in the convex hull

[edit]

Wendel's theorem gives the probability that, under certain symmetry assumptions, the convex hull of i.i.d. points does not contain the origin.

Theorem (Wendel, 1962[4]) — Let be integers. Assume that is rotationally invariant and assign measure to any linear hyperplane. Then

A generalization by Wagner and Welzl says that if the symmetry assumption is dropped then the equality is replaced by an inequality.

Theorem (Wagner and Welzl, 2001[5]) — Let be integers. Assume that is absolutely continuous with respect to the Lebesgue measure. Then Equality holds if and only if the measure of any measurable cone is equal to the measure of its symmetry , equivalently for any Borel set .

Random simplices

[edit]

If then is a random simplex. This simplex has dimension almost surely (assuming that for any -dimensional affine space). The expectation and higher moments of the volume have been computed explicitly when the points are distributed uniformly in a Euclidean ball or sphere.[6]

Volume moments of random simplex (vertices uniformly distributed in a ball). — Let be integers with and . The convex hull of independent points uniformly distributed either in unit ball or the unit sphere of the -dimensional Euclidean is almost surely a -dimensional simplex. Its volume has -th moment if all the points are distributed in the ball, and if all the points are distributed in the sphere, where denotes the volume of the -dimensional Euclidean unit ball, the surface area of its boundary, and

References

[edit]
  1. ^ Sylvester, J.J. (April 1864). "Question 1491". The Educational Times (London).
  2. ^ Pfiefer, Richard E. (December 1989). "The Historical Development of J. J. Sylvester's Four Point Problem". Mathematics Magazine. 62: 309–317. doi:10.1080/0025570X.1989.11977460 – via JSTOR.
  3. ^ "Sylvester's Four-point problem (MathWorld)".{{cite web}}: CS1 maint: url-status (link)
  4. ^ Wendel, J. G. (1962-06-01). "A Problem in Geometric Probability". MATHEMATICA SCANDINAVICA. 11: 109–112. doi:10.7146/math.scand.a-10655. ISSN 1903-1807.
  5. ^ Wagner, Uli; Welzl, Emo (2000-05-01). "Origin-embracing distributions or a continuous analogue of the upper bound theorem". Proceedings of the sixteenth annual symposium on Computational geometry. SCG '00. Clear Water Bay, Kowloon, Hong Kong: Association for Computing Machinery: 50–56. doi:10.1145/336154.336176. ISBN 978-1-58113-224-3.
  6. ^ Schneider, Rolf (2008). Stochastic and integral geometry. Wolfgang Weil. Berlin: Springer. Theorem 8.2.3. ISBN 978-3-540-78859-1. OCLC 288565837.

External links

[edit]