2023/07/11 by Brett Leroux, Leroux, Brett
Computer Science · Engineering · Mathematics · #52A22 #52B05 #52B35 #52C45 #60D05 #Automated Road and Building Extraction #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #Point processes and geometric inequalities #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2307.05817
openalex publication_date 2023/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let μ be a probability distribution on ℝd which assigns measure zero to every hyperplane and S a set of points sampled independently from μ. What can be said about the expected combinatorial structure of the convex hull of S? These polytopes are simplicial with probability one, but not much else is known except when more restrictive assumptions are imposed on μ. In this paper we show that, with probability close to one, the convex hull of S has a high degree of neighborliness no matter the underlying distribution μ as long as n is not much bigger than d. As a concrete example, our result implies that if for each d in ℕ we choose a probability distribution μd on ℝd which assigns measure zero to every hyperplane and then set Pn to be the convex hull of an i.i.d. sample of n ≤ 5d/4 random points from μd, the probability that Pn is k-neighborly approaches one as d → ∞ for all k≤ d/20. We also give a simple example of a family of distributions which essentially attain our lower bound on the k-neighborliness of a random polytope.