License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.18
URN: urn:nbn:de:0030-drops-160269
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16026/
Bonnet, Gilles ;
Dadush, Daniel ;
Grupel, Uri ;
Huiberts, Sophie ;
Livshyts, Galyna
Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
Abstract
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)}).
BibTeX - Entry
@InProceedings{bonnet_et_al:LIPIcs.SoCG.2022.18,
author = {Bonnet, Gilles and Dadush, Daniel and Grupel, Uri and Huiberts, Sophie and Livshyts, Galyna},
title = {{Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {18:1--18:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16026},
URN = {urn:nbn:de:0030-drops-160269},
doi = {10.4230/LIPIcs.SoCG.2022.18},
annote = {Keywords: Random Polytopes, Combinatorial Diameter, Hirsch Conjecture}
}
|
Keywords: |
|
Random Polytopes, Combinatorial Diameter, Hirsch Conjecture |
|
Collection: |
|
38th International Symposium on Computational Geometry (SoCG 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.06.2022 |
