2026-07-22T10:24:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16026 2024-03-06T10:56:46Z ddc:004 open_access

Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes Bonnet, Gilles Dadush, Daniel Grupel, Uri Huiberts, Sophie Livshyts, Galyna Random Polytopes Combinatorial Diameter Hirsch Conjecture The combinatorial diameter diam(P) of a polytope P is the maximum shortest path distance between any pair of vertices. In this paper, we provide upper and lower bounds on the combinatorial diameter of a random "spherical" polytope, which is tight to within one factor of dimension when the number of inequalities is large compared to the dimension. More precisely, for an n-dimensional polytope P defined by the intersection of m i.i.d. half-spaces whose normals are chosen uniformly from the sphere, we show that diam(P) is Ω(n m^{1/(n-1)}) and O(n² m^{1/(n-1)} + n⁵ 4ⁿ) with high probability when m ≥ 2^{Ω(n)}. For the upper bound, we first prove that the number of vertices in any fixed two dimensional projection sharply concentrates around its expectation when m is large, where we rely on the Θ(n² m^{1/(n-1)}) bound on the expectation due to Borgwardt [Math. Oper. Res., 1999]. To obtain the diameter upper bound, we stitch these "shadows paths" together over a suitable net using worst-case diameter bounds to connect vertices to the nearest shadow. For the lower bound, we first reduce to lower bounding the diameter of the dual polytope P^∘, corresponding to a random convex hull, by showing the relation diam(P) ≥ (n-1)(diam(P^∘)-2). We then prove that the shortest path between any "nearly" antipodal pair vertices of P^∘ has length Ω(m^{1/(n-1)}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gilles Bonnet and Daniel Dadush and Uri Grupel and Sophie Huiberts and Galyna Livshyts 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.18 urn:nbn:de:0030-drops-160269 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.18 eng https://creativecommons.org/licenses/by/4.0/legalcode