Doubly random polytopes

DOI10.1002/RSA.21059arXiv2006.07000OpenAlexW3211940595MaRDI QIDQ6052467FDOQ6052467

Andrew Newman

Publication date: 17 October 2023

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

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

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)

Cites Work

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

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)