Doubly random polytopes

DOI10.1002/RSA.21059MaRDI QIDQ6052467zbMATH OpenOpenAlexFDO

Authors Andrew Newman

Publication date 17 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2006.07000

zbMATH Keywords

Hausdorff distancerandom graphsprobabilistic methodrandom polytopesellipsoid and polytopes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Random convex sets and integral geometry (aspects of convex geometry) (52A22)

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 $mathbb{R}^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$.

Recommendations

• The convex hull of random points on the boundary of a simple polytope
• On the Number of Vertices of Random Polyhedra with a Given Number of Facets
• The combinatorial structure of random polytopes
• Intrinsic volumes and f-vectors of random polytopes
• The convex hull of a uniform sample from the interior of a simple d-polytope

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 1975233 (Why is no real title available?)
• scientific article; zbMATH DE number 1538119 (Why is no real title available?)
• scientific article; zbMATH DE number 3224041 (Why is no real title available?)
• Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points
• Average-case analysis of the double description method and the beneath-beyond algorithm
• Central limit theorems for random polytopes
• Expected Number of Vertices of a Random Convex Polyhedron
• Integer Programming and Combinatorial Optimization
• Intrinsic volumes and f-vectors of random polytopes
• Intrinsic volumes of inscribed random polytopes in smooth convex bodies
• Lectures on Polytopes
• On 0-1 polytopes with many facets
• On the Probability That a Random ± 1-Matrix Is Singular
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
• Random points on the boundary of smooth convex bodies
• Random polytopes and the Efron-Stein jackknife inequality.
• Random polytopes in the d-dimensional cube
• Stochastical approximation of convex bodies
• Surface bodies and \(p\)-affine surface area
• The Probability that a Random Polytope is Bounded
• The jackknife estimate of variance
• The limit shape of the zero cell in a stationary Poisson hyperplane tessellation.
• The number of trees
• The probabilistic method
• polymake: a framework for analyzing convex polytopes

Cited in

(1)

• The convex hull of random points on the boundary of a simple polytope

This page was built for publication: Doubly random polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6052467)