Doubly random polytopes. Issue 2 (12th November 2021)

• Record Type: Journal Article
• Authors: Newman, Andrew
• Is Part Of: Random structures & algorithms. Volume 61:Issue 2(2022)
• Page Start: 364
• Page End: 382
• Publication Date: 2021-11-12
• Subjects: probabilistic method -- random graphs -- random polytopes; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21059
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: A two‐step model for generating random polytopes is considered. For parameters d, m, and p, the first step is to generate a simple polytope P whose facets are given by m uniform random hyperplanes tangent to the unit sphere in ℝ d, and the second step is to sample each vertex of P independently with probability p and let Q be the convex hull of the sampled vertices. We establish results on how well Q approximates the unit sphere in terms of m and p as well as asymptotics on the combinatorial complexity of Q for certain regimes of p .