2022

11. Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes (Proceeding)
    Gilles Bonnet, Daniel Dadush, Uri Grupel, Sophie Huiberts and Galyna Livshyts
    Proceeding of the 38th International Symposium on Computational Geometry (SoCG 2022)

    Abstract

    The combinatorial diameter $\operatorname{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 $\operatorname{diam}(P)$ is $\Omega(nm^{\frac{1}{n-1}})$ and $O(n^2 m^{\frac{1}{n-1}} + n^5 4^n)$ with high probability when $m \geq 2^{\Omega(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 $\Theta(n^2 m^{\frac{1}{n-1}})$ bound on the expectation due to Borgwardt [Math. Oper. Res., 1999]. To obtain the diameter upper bound, we stitch these \textit{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^\circ$, corresponding to a random convex hull, by showing the relation $\operatorname{diam}(P) \geq (n-1)(\operatorname{diam}(P^\circ)-2)$. We then prove that the shortest path between any ``nearly’’ antipodal pair vertices of $P^\circ$ has length $\Omega(m^{\frac{1}{n-1}})$.

    Keywords

    Random Polytopes, Combinatorial Diameter, Hirsch Conjecture.

    Link(s)

    SoCG arXiv
10. Facets of spherical random polytopes
    Gilles Bonnet and Eliza O'Reilly
    Mathematische Nachrichten, vol 295

    Abstract

    Facets of the convex hull of $n$ independent random vectors chosen uniformly at random from the unit sphere in $\mathbb{R}^d$ are studied. A particular focus is given on the height of the facets as well as the expected number of facets as the dimension increases. Regimes for $n$ and $d$ with different asymptotic behavior of these quantities are identified and asymptotic formulas in each case are established. Extensions of some known results in fixed dimension to the case where dimension tends to infinity are described.

    Link(s)

    Math. Nachr. arXiv

    Image(s)

    

    Video

9. Weak convergence of the intersection point process of Poisson hyperplanes
   Anastas Baci, Gilles Bonnet and Christoph Thäle
   Annales de l'Institut Henri Poincaré (B) Probabilités et Statistique, vol 58, no 2

   Abstract

   This paper deals with the intersection point process of a stationary and isotropic Poisson hyperplane process in $\mathbb{R}^d$ of intensity $t>0$, where only hyperplanes that intersect a centred ball of radius $R>0$ are considered. Taking $R=t^{-\frac{d}{d+1}}$ it is shown that this point process converges in distribution, as $t\to\infty$, to a Poisson point process on $\mathbb{R}^d\setminus{0}$ whose intensity measure has power-law density proportional to $|x|^{-(d+1)}$ with respect to the Lebesgue measure. A bound on the speed of convergence in terms of the Kantorovich-Rubinstein distance is provided as well. In the background is a general functional Poisson approximation theorem on abstract Poisson spaces. Implications on the weak convergence of the convex hull of the intersection point process and the convergence of its $f$-vector are also discussed, disproving and correcting thereby a conjecture of Devroye and Toussaint [J.\ Algorithms 14.3 (1993), 381–394] in computational geometry.

   Visualization

   In the Geogebra applet below you can visualize the intersection process derived from up to 30 i.i.d. lines uniformly distributed among the lines intersecting the unit disc. If you have some troubles with the zoom, you can also try to follow this link and click on the bottom right of the applet to activate the full screen mode.
   

   Keywords

   convex hull, integral geometry, intersection point process, Poisson hyperplane process, Poisson point process approximation, rate of convergence, weak convergence.

   Link(s)

   AHP arXiv

   Image(s)

   

   Video

2021

8. Sharp inequalities for the mean distance of random points in convex bodies
   Gilles Bonnet, Anna Gusakova, Christoph Thäle and Dmitry Zaporozhets
   Advances in Mathematics, vol 386

   Abstract

   For a convex body $K\subset\mathbb{R}^d$ the mean distance $\Delta(K)=\mathbb{E}|X-Y|$ is the expected Euclidean distance of two independent and uniformly distributed random points $X,Y\in K$. Optimal lower and upper bounds for ratio between $\Delta(K)$ and the first intrinsic volume $V_1(K)$ of $K$ (normalized mean width) are derived and degenerate extremal cases are discussed. The argument relies on Riesz’s rearrangement inequality and the solution of an optimization problem for powers of concave functions. The relation with results known from the existing literature is reviewed in detail.

   Keywords

   Concave funcion, convex body, geometric extremum problem, geometric inequality, intrinsic volume, mean distance, Riesz rearrangement inequality, sharp geometric inequality.

   Link(s)

   Adv. Math. arXiv

   Image(s)

   
7. Phase transition for the volume of high-dimensional random polytopes
   Gilles Bonnet, Zakhar Kabluchko and Nicola Turchi
   Random Structures and Algorithms, vol 58

   Abstract

   The beta polytope $P_{n,d}^\beta$ is the convex hull of $n$ i.i.d. random points distributed in the unit ball of $\mathbb{R}^d$ according to a density proportional to $(1-\lVert{x}\rVert^2)^{\beta}$ if $\beta>-1$ (in particular, $\beta=0$ corresponds to the uniform distribution in the ball), or uniformly on the unit sphere if $\beta=-1$. We show that the expected normalized volumes of high-dimensional beta polytopes exhibit a phase transition and we describe its shape. We derive analogous results for the intrinsic volumes of beta polytopes and, when $\beta=0$, their number of vertices.

   Keywords

   Beta distribution, convex hull, expected volume, phase transition, random polytopes.

   Link(s)

   RSA arXiv

   Image(s)

   

   Video

2020

6. The maximal degree in a Poisson-Delaunay graph
   Gilles Bonnet and Nicolas Chenavier
   Bernouilli, vol 26, no 2

   Abstract

   We investigate the maximal degree in a Poisson-Delaunay graph in $\mathbf{R}^d$, $d\geq 2$, over all nodes in the window $\mathbf{W}_\rho:= \rho^{1/d}[0,1]^d$ as $\rho$ goes to infinity. The exact order of this maximum is provided in any dimension. In the particular setting $d=2$, we show that this quantity is concentrated on two consecutive integers with high probability. An extension of this result is discussed when $d\geq 3$.

   Keywords

   degree, Delaunay graph, extreme values, Poisson point process.

   Link(s)

   Bernoulli arXiv

   Image(s)

   

2019

5. Threshold phenomena for high-dimensional random polytopes
   Gilles Bonnet, Giorgos Chasapis, Julian Grote, Daniel Temesvari and Nicola Turchi
   Communications in Comtemporary Mathematics, vol 21, no 5

   Abstract

   Let $X_1,\ldots,X_N$, $N>n$, be independent random points in $\mathbb{R}^n$, distributed according to the so-called beta or beta-prime distribution, respectively. We establish threshold phenomena for the volume, intrinsic volumes, or more general measures of the convex hulls of these random point sets, as the space dimension $n$ tends to infinity. The dual setting of polytopes generated by random halfspaces is also investigated.

   Keywords

   Beta distribution, beta-prime distribution, convex bodies, isotropic log-concave measures, phase transition, random polytopes, volume threshold.

   Link(s)

   Commun. Contemp. Math. arXiv

   Image(s)

   

2018

4. Cells with many facets in a Poisson hyperplane tessellation
   Gilles Bonnet, Pierre Calka and Matthias Reitzner
   Advances in Mathematics, vol 324

   Abstract

   Let $Z$ be the typical cell of a stationary Poisson hyperplane tessellation in $\mathbb{R}^d$. The distribution of the number of facets $f(Z)$ of the typical cell is investigated. It is shown, that under a well-spread condition on the directional distribution, the quantity $n^{\frac{2}{d-1}}\sqrt[n]{\mathbb{P}(f(Z)=n)}$ is bounded from above and from below. When $f(Z)$ is large, the isoperimetric ratio of $Z$ is bounded away from zero with high probability. These results rely on one hand on the Complementary Theorem which provides a precise decomposition of the distribution of $Z$ and on the other hand on several geometric estimates related to the approximation of polytopes by polytopes with fewer facets. From the asymptotics of the distribution of $f(Z)$, tail estimates for the so-called $\Phi$ content of $Z$ are derived as well as results on the conditional distribution of $Z$ when its $\Phi$ content is large.

   Keywords

   Poisson hyperplane tessellation, random polytopes, typical cell, directional distribution, Complementary Theorem, D.G. Kendall's problem.

   Link(s)

   Adv. Math. arXiv

   Image(s)

   
3. Polytopal approximation of elongated convex bodies
   Gilles Bonnet
   Advances in Geometry, vol 18, no 1

   Abstract

   This paper presents bounds for the best approximation, with respect to the Hausdorff metric, of a convex body $K$ by a circumscribed polytope $P$ with a given number of facets. These bounds are of particular interest if $K$ is elongated. To measure the elongation of the convex set, its isoperimetric ratio $ V_j(K)^{1/j} V_i(K)^{-1/i} $ is used.

   Keywords

   polytopal approximation, elongated convex bodies, isoperimetric ratio, δ-net.

   Link(s)

   Adv. Geom. arXiv

   Image(s)

   
2. Small cells in a Poisson hyperplane tessellation
   Gilles Bonnet
   Advances in Applied Mathematics, vol 95

   Abstract

   Until now, little was known about properties of small cells in a Poisson hyperplane tessellation. The few existing results were either heuristic or applying only to the two dimensional case and for very specific size functionals and directional distributions. This paper fills this gap by providing a systematic study of small cells in a Poisson hyperplane tessellation of arbitrary dimension, arbitrary directional distribution $\varphi$ and with respect to an arbitrary size functional $\Sigma$. More precisely, we investigate the distribution of the typical cell $Z$, conditioned on the event $ { \Sigma(Z) < a }$, where $a\to0$ and $\Sigma$ is a size functional, i.e. a functional on the set of convex bodies which is continuous, not identically zero, homogeneous of degree $k>0$, and increasing with respect to set inclusion. We focus on the number of facets and the shape of such small cells. We show in various general settings that small cells tend to minimize the number of facets and that they have a non degenerated limit shape distribution which depends on the size $\Sigma$ and the directional distribution. We also exhibit a class of directional distribution for which cells with small inradius do not tend to minimize the number of facets.

   Keywords

   Poisson hyperplane tessellation, typical cell, small cells, number of facets, shape, size functional.

   Link(s)

   Adv. in Appl. Math. arXiv

   Image(s)

   

2017

1. Monotonicity of facet numbers of random convex hulls
   Gilles Bonnet, Julian Grote, Daniel Temesvari, Christoph Thäle, Nicola Turchi and Florian Wespi
   Journal of Mathematical Analysis and Applications, vol 455, no 2

   Abstract

   Let $X_1,\ldots,X_n$ be independent random points that are distributed according to a probability measure on $\mathbb{R}^d$ and let $P_n$ be the random convex hull generated by $X_1,\ldots,X_n$ ($n\geq d+1$). Natural classes of probability distributions are characterized for which, by means of Blaschke-Petkantschin formulae from integral geometry, one can show that the mean facet number of $P_n$ is strictly monotonically increasing in $n$.

   Keywords

   Blaschke–Petkantschin formula, mean facet number, random convex hull.

   Link(s)

   J. Math. Anal. Appl. arXiv

   Image(s)

   

2016

• Poisson hyperplane tessellation: Asymptotic probabilities of the zero and typical cells
  Gilles Bonnet
  

  Abstract

  We consider the distribution of the zero and typical cells of a (homogeneous) Poisson hyperplane tessellation. We give a direct proof adapted to our setting of the well known Complementary Theorem. We provide sharp bounds for the tail distribution of the number of facets. We also improve existing bounds for the tail distribution of size measurements of the cells, such as the volume or the mean width. We improve known results about the generalised D.G. Kendall’s problem, which asks about the shape of large cells. We also show that cells with many facets cannot be close to a lower dimensional convex body. We tacle the much less study problem of the number of facets and the shape of small cells. In order to obtain the results above we also develop some purely geometric tools, in particular we give new results concerning the polytopal approximation of an elongated convex body.

  Keywords

  stochastic geometry, convex geometry, tessellation, mosaic, random tessellation, Poisson hyperplane tessellation, zero cell, typical cell, asymptotic probabilities, D.G. Kendall's problem, Complementary Theorem, polytopal approximation, delta-net, elongated convex bodies, geometric integral transformation formulae, facets, phi-Content, center, shape, tail distribution, small cells.

  Link(s)

  UOS Repositorium

  Image(s)