Profiles
All my publications are listed here, but you can also find them in various corners of the Internet:Coauthors
Publications
Submitted

Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
(Journal version)
Gilles Bonnet, Daniel Dadush, Uri Grupel, Sophie Huiberts and Galyna Livshyts
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.\ halfspaces whose normals are chosen uniformly from the sphere, we show that $\operatorname{diam}(P)$ is $\Omega(nm^{\frac{1}{n1}})$ and $O(n^2 m^{\frac{1}{n1}} + 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}{n1}})$ 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 worstcase 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 (n1)(\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}{n1}})$.
Link(s)

Limit theory of sparse random geometric graphs in high dimensions
Gilles Bonnet, Christian Hirsch, Daniel Rosen and Daniel Willhalm
Abstract
We study topological and geometric functionals of $l_\infty$random geometric graphs on the highdimensional torus in a sparse regime, where the expected number of neighbors decays exponentially in the dimension. More precisely, we establish moment asymptotics, functional central limit theorems and Poisson approximation theorems for certain functionals that are additive under disjoint unions of graphs. For instance, this includes simplex counts and Betti numbers of the Rips complex, as well as general subgraph counts of the random geometric graph. We also present multiadditive extensions that cover the case of persistent Betti numbers of the Rips complex.
Link(s)
Published
2022

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.\ halfspaces whose normals are chosen uniformly from the sphere, we show that $\operatorname{diam}(P)$ is $\Omega(nm^{\frac{1}{n1}})$ and $O(n^2 m^{\frac{1}{n1}} + 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}{n1}})$ 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 worstcase 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 (n1)(\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}{n1}})$.
Keywords
Random Polytopes, Combinatorial Diameter, Hirsch Conjecture.
Link(s)

Facets of spherical random polytopes
Gilles Bonnet and Eliza O'Reilly
Mathematische Nachrichten, vol 295Abstract
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)
Image(s)
Video

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 2Abstract
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 powerlaw density proportional to $x^{(d+1)}$ with respect to the Lebesgue measure. A bound on the speed of convergence in terms of the KantorovichRubinstein 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)
Image(s)
Video
2021

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 386Abstract
For a convex body $K\subset\mathbb{R}^d$ the mean distance $\Delta(K)=\mathbb{E}XY$ 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)
Image(s)

Phase transition for the volume of highdimensional random polytopes
Gilles Bonnet, Zakhar Kabluchko and Nicola Turchi
Random Structures and Algorithms, vol 58Abstract
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 highdimensional 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)
Image(s)
Video
2020

The maximal degree in a PoissonDelaunay graph
Gilles Bonnet and Nicolas Chenavier
Bernouilli, vol 26, no 2Abstract
We investigate the maximal degree in a PoissonDelaunay 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)
Image(s)
2019

Threshold phenomena for highdimensional random polytopes
Gilles Bonnet, Giorgos Chasapis, Julian Grote, Daniel Temesvari and Nicola Turchi
Communications in Comtemporary Mathematics, vol 21, no 5Abstract
Let $X_1,\ldots,X_N$, $N>n$, be independent random points in $\mathbb{R}^n$, distributed according to the socalled beta or betaprime 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, betaprime distribution, convex bodies, isotropic logconcave measures, phase transition, random polytopes, volume threshold.
Link(s)
Image(s)
2018

Cells with many facets in a Poisson hyperplane tessellation
Gilles Bonnet, Pierre Calka and Matthias Reitzner
Advances in Mathematics, vol 324Abstract
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 wellspread condition on the directional distribution, the quantity $n^{\frac{2}{d1}}\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 socalled $\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)
Image(s)

Polytopal approximation of elongated convex bodies
Gilles Bonnet
Advances in Geometry, vol 18, no 1Abstract
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)
Image(s)

Small cells in a Poisson hyperplane tessellation
Gilles Bonnet
Advances in Applied Mathematics, vol 95Abstract
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)
Image(s)
2017

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 2Abstract
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 BlaschkePetkantschin 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)
Image(s)
Ph.D. Thesis
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, deltanet, elongated convex bodies, geometric integral transformation formulae, facets, phiContent, center, shape, tail distribution, small cells.
Link(s)
Image(s)