Convex hulls of perturbed random point sets

We consider the convex hull of the perturbed point process comprised of $n$ i.i.d. points, each distributed as the sum of a uniform point on the unit sphere $S^{d-1}$ and a uniform point in the $d$-dimensional ball centered at the origin and of radius $n^{alpha}, alpha in (-infty, infty)$. This model, inspired by the smoothed complexity analysis introduced in computational geometry cite{DGGT,ST}, is a perturbation of the classical random polytope. We show that the perturbed point process, after rescaling, converges in the scaling limit to one of five Poisson point processes according to whether $alpha$ belongs to one of five regimes. The intensity measure of the limit Poisson point process undergoes a transition at the values $alpha = frac{-2} {d -1}$ and $alpha = frac{2} {d + 1}$ and it gives rise to four rescalings for the $k$-face functional on perturbed data. These rescalings are used to establish explicit expectation asymptotics for the number of $k$-dimensional faces of the convex hull of either perturbed binomial or Poisson data. In the case of Poisson input, we establish explicit variance asymptotics and a central limit theorem for the number of $k$-dimensional faces. Finally it is shown that the rescaled boundary of the convex hull of the perturbed point process converges to the boundary of a parabolic hull process.

Mean asymptotics for a Poisson-Voronoi cell on a Riemannian manifold

In this paper, we consider a Riemannian manifold $M$ and the Poisson-Voronoi tessellation generated by the union of a fixed point $x_0$ and a Poisson point process of intensity $lambda$ on $M$. We obtain asymptotic expansions up to the second order for the means of several characteristics of the Voronoi cell associated with $x_0$, including its volume and number of vertices. In each case, the first term of the estimate is equal to the mean characteristic in the Euclidean setting while the second term may contain a particular curvature of $M$ at $x_0$: the scalar curvature in the case of the mean number of vertices, the Ricci curvature in the case of the density of vertices and the sectional curvatures in the cases of the volume and number of vertices of a section of the Voronoi cell. Several explicit formulas are also derived in the particular case of constant curvature. The key tool for proving these results is a new change of variables formula of Blaschke-Petkantschin type in the Riemannian setting. Finally, a probabilistic proof of the Gauss-Bonnet Theorem is deduced from the asymptotic estimate of the total number of vertices of the tessellation in dimension two.

The Poisson-Voronoi cell around an isolated nucleus

Consider a planar random point process made of the union of a point (the origin) and of a Poisson point process with a uniform intensity outside a deterministic set surrounding the origin. When the intensity goes to infinity, we show that the Voronoi cell associated with the origin converges from above to a deterministic convex set. We describe this set and give the asymptotics of the expectation of its defect area, defect perimeter and number of vertices. On the way, two intermediary questions are treated. First, we describe the mean characteristics of the Poisson-Voronoi cell conditioned on containing a fixed convex body around the origin and secondly, we show that the nucleus of such cell converges to the Steiner point of the convex body. As in Renyi and Sulankes seminal papers on random convex hulls, the regularity of the convex body has crucial importance. We deal with both the smooth and polygonal cases. Techniques are based notably on accurate estimates of the area of the Voronoi flower and of the support function of the cell containing the origin as well as on an Efron-type relation.

Cells with many facets in a Poisson hyperplane tessellation

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.

Variance Asymptotics and Scaling Limits for Random Polytopes

Let K be a convex set in R d and let K $lambda$ be the convex hull of a homogeneous Poisson point process P $lambda$ of intensity $lambda$ on K. When K is a simple polytope, we establish scaling limits as $lambda$ $rightarrow$ $infty$ for the boundary of K $lambda$ in a vicinity of a vertex of K and we give variance asymptotics for the volume and k-face functional of K $lambda$, k $in$ {0, 1, ..., d -- 1}, resolving an open question posed in [18]. The scaling limit of the boundary of K $lambda$ and the variance asymptotics are described in terms of a germ-grain model consisting of cone-like grains pinned to the extreme points of a Poisson point process on R d--1 $times$ R having intensity $sqrt$ de dh dhdv.

Variance asymptotics and scaling limits for Gaussian Polytopes

Let $K_n$ be the convex hull of i.i.d. random variables distributed according to the standard normal distribution on $R^d$. We establish variance asymptotics as $n to infty$ for the re-scaled intrinsic volumes and $k$-face functionals of $K_n$, $k in {0,1,...,d-1}$, resolving an open problem. Variance asymptotics are given in terms of functionals of germ-grain models having parabolic grains with apices at a Poisson point process on $R^{d-1} times R$ with intensity $e^h dh dv$. The scaling limit of the boundary of $K_n$ as $n to infty$ converges to a festoon of parabolic surfaces, coinciding with that featuring in the geometric construction of the zero viscosity solution to Burgers equation with random input.

Extreme values for characteristic radii of a Poisson-Voronoi tessellation

A homogeneous Poisson-Voronoi tessellation of intensity $gamma$ is observed in a convex body $W$. We associate to each cell of the tessellation two characteristic radii: the inradius, i.e. the radius of the largest ball centered at the nucleus and included in the cell, and the circumscribed radius, i.e. the radius of the smallest ball centered at the nucleus and containing the cell. We investigate the maximum and minimum of these two radii over all cells with nucleus in $W$. We prove that when $gammarightarrowinfty$, these four quantities converge to Gumbel or Weibull distributions up to a rescaling. Moreover, the contribution of boundary cells is shown to be negligible. Such approach is motivated by the analysis of the global regularity of the tessellation. In particular, consequences of our study include the convergence to the simplex shape of the cell with smallest circumscribed radius and an upper-bound for the Hausdorff distance between $W$ and its so-called Poisson-Voronoi approximation.

Fractal random series generated by Poisson-Voronoi tessellations

In this paper, we construct a new family of random series defined on $R^D$, indexed by one scaling parameter and two Hurst-like exponents. The model is close to Takagi-Knopp functions, save for the fact that the underlying partitions of $R^D$ are not the usual dyadic meshes but random Voronoi tessellations generated by Poisson point processes. This approach leads us to a continuous function whose random graph is shown to be fractal with explicit and equal box and Hausdorff dimensions. The proof of this main result is based on several new distributional properties of the Poisson-Voronoi tessellation on the one hand, an estimate of the oscillations of the function coupled with an application of a Frostman-type lemma on the other hand. Finally, we introduce two related models and provide in particular a box-dimension calculation for a derived deterministic Takagi-Knopp series with hexagonal bases.

Variance asymptotics for random polytopes in smooth convex bodies

Let $K subset R^d$ be a smooth convex set and let $P_la$ be a Poisson point process on $R^d$ of intensity $la$. The convex hull of $P_la cap K$ is a random convex polytope $K_la$. As $la to infty$, we show that the variance of the number of $k$-dimensional faces of $K_la$, when properly scaled, converges to a scalar multiple of the affine surface area of $K$. Similar asymptotics hold for the variance of the number of $k$-dimensional faces for the convex hull of a binomial process in $K$.

Asymptotics of visibility in the hyperbolic plane

At each point of a Poisson point process of intensity $lambda$ in the hyperbolic place, center a ball of bounded random radius. Consider the probability $P_r$ that from a fixed point, there is some direction in which one can reach distance $r$ without hitting any ball. It is known cite{BJST} that if $lambda$ is strictly smaller than a critical intensity $lambda_{gv}$ then $P_r$ does not go to $0$ as $rto infty$. The main result in this note shows that in the case $lambda=lambda_{gv}$, the probability of reaching distance larger than $r$ decays essentially polynomial, while if $lambda>lambda_{gv}$, the decay is exponential. We also extend these results to various related models.