{
  "id": "enwiki-001373728986",
  "slug": "random-polytope",
  "title": "Random polytope",
  "qid": "",
  "lead": "In mathematics, a random polytope is a structure commonly used in convex analysis and the analysis of linear programs in d-dimensional Euclidean space \\R^d . Depending on use the construction and definition, random polytopes may differ.",
  "body": "In mathematics, a random polytope is a structure commonly used in convex analysis and the analysis of linear programs in d-dimensional Euclidean space \\R^d . Depending on use the construction and definition, random polytopes may differ. The following parameterization has been used: r:(\\R^d \\times \\{0,1\\})^m\\rightarrow \\text{Polytopes} \\in \\R^d such that r((p_1, 0), (p_2, 1), (p_3, 1)...(p_m, i_m)) = \\{x \\in \\R^n: | \\frac{p_j} \\cdot x \\leq ||p_j|| \\text{ if } i_j=1, \\frac{p_j} \\cdot x \\geq ||p_j|| \\text{ if } i_j=0 \\} (Note: these polytopes can be empty). Let \\Kappa be the set of convex bodies in \\R^d . Assume K \\in\\Kappa 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 \\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 \\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. Assume we are given a multivariate probability distribution on (\\R^d \\times \\{ 0, 1\\})^m=(p_1\\times i_1,\\dots,p_m\\times i_m)^m that is Absolutely continuous on (p_1,\\dots,p_d) with respect to Lebesgue measure. Generates either 0 or 1 for the i s with probability of \\frac{1}{2} each. Assigns a measure of 0 to the set of elements in (\\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 \\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 ).",
  "categories": [
    "20160173",
    "20476826",
    "23603337",
    "26220375",
    "29176236"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1373728986",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1788791410.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001373728986",
    "type": "webpage",
    "title": "Random polytope",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/random-polytope",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001373728986",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1373728986",
    "note": "Immutable snapshot enwiki-001373728986"
  }
}