# Random approximation of convex bodies in
Hausdorff metric

Joscha Prochno111Faculty of Computer Science and Mathematics, University of
Passau, Dr.-Hans-Kapfinger-Str. 30, 94032 Passau, Germany, joscha.prochno@uni-
passau.de<EMAIL_ADDRESS>Carsten Schütt222Department of
Mathematics, University of Kiel, Heinrich-Hecht-Platz 6, 24118 Kiel, Germany,
<EMAIL_ADDRESS>, Mathias Sonnleitner∗, Elisabeth M.
Werner333Department of Mathematics, Case Western Reserve University, 2145
Adalbert Road, Cleveland, OH 44106, USA<EMAIL_ADDRESS>
###### Abstract

While there is extensive literature on approximation, deterministic as well as
random, of general convex bodies $K$ in the symmetric difference metric, or
other metrics arising from intrinsic volumes, very little is known for
corresponding random results in the Hausdorff distance when the approximant
$K_{n}$ is given by the convex hull of $n$ independent random points chosen
uniformly on the boundary or in the interior of $K$. When $K$ is a polygon and
the points are chosen on its boundary, we determine the exact limiting
behavior of the expected Hausdorff distance between a polygon as $n\to\infty$.
From this we derive the behavior of the asymptotic constant for a regular
polygon in the number of vertices.

##  1 Introduction

A convex body $K$ in $\mathbb{R}^{d}$ can be approximated arbitrarily well by
polytopes in the symmetric difference metric or the Hausdorff metric. This can
be achieved in many ways. For instance, by taking the convex hull of
sufficiently many random points sampled inside the convex body $K$ or on its
boundary $\partial K$. In this paper we investigate how much a convex body $K$
differs from the convex hull $K_{n}$ of $n\in\mathbb{N}$ points chosen at
random from $K$. More specifically, we are interested in the order of
magnitude of the following two quantities

$\mathbb{P}(\delta_{H}(K,K_{n})\geq t),\quad t>0,\hskip
56.9055pt\mbox{and}\hskip 56.9055pt\mathbb{E}[\delta_{H}(K,K_{n})],$

where the points spanning the polytope $K_{n}$ are chosen uniformly at random
either from $K$ or from the boundary of $K$, with respect to the normalized
Hausdorff measure of appropriate dimension. We refer to the end of this
section for the definitions of the relevant notions.

There is a vast amount of literature on these problems when the error of
approximation is measured by the expectation of the symmetric difference
metric $d_{S}$: for points chosen uniformly at random inside the body, A.
Rényi and R. Sulanke studied this question in dimension $2$ [13, 14]; I.
Bárány proved asymptotics involving the Gauß-Kronecker curvature for smooth
convex bodies in arbitrary dimension [2]; C. Schütt generalized this to
arbitrary convex bodies in [16]. In [3], I. Bárány and Ch. Buchta determined
the asymptotic behavior of the expected symmetric difference metric for convex
polytopes in arbitrary dimensions.

More recently, M. Reitzner [11] and C. Schütt and E. M. Werner [17] proved
asymptotics for $\mathbb{E}[d_{S}(K,K_{n})]$ for random points chosen from the
boundary of a sufficiently smooth convex body. In [12] these three authors
extended these results to the case when the convex bodies are polytopes.

The extensive literature on approximation of general convex bodies,
deterministic as well as random, mostly involves the symmetric difference
metric, or other metrics coming from intrinsic volumes. For smooth convex
bodies the asymptotic constants are often given as integrals of curvature(s)
of $K$ over its boundary and for polytopes combinatorial quantities appear.
For more information, we refer to the survey [10]. However, very little is
known for corresponding results in the Hausdorff distance and, for the
reader’s convenience, we provide a short overview.

S. Glasauer and R. Schneider [7] considered the case of a convex body with
$C^{3}_{+}$-boundary, that is three times continuously differentiable boundary
with everywhere positive curvature, and a probability measure $\mathbb{P}$
with density $h>0$ of class $C^{1}$ on the boundary. For random points sampled
according to this density they proved the asymptotics

$\hskip-14.22636pt\left(\frac{n}{\log
n}\right)^{\frac{2}{d-1}}\delta_{H}(K,K_{n})\xrightarrow[n\to\infty]{\mathbb{P}}\frac{1}{2}\left(\frac{1}{\operatorname{vol}_{d-1}(B_{2}^{d-1})}\max_{x\in\partial
K}\frac{\sqrt{\kappa_{K}(x)}}{h(x)}\right)^{\frac{2}{d-1}},$ (1)

where $\kappa_{K}$ is the Gauß-Kronecker curvature, $B_{2}^{d-1}$ the
$(d-1)$-dimensional unit ball and $\xrightarrow[n\to\infty]{\mathbb{P}}$
denotes convergence in probability as $n\to\infty$. The case $d=2$ was already
obtained by R. Schneider [15].

L. Dümbgen and G. Walther [6] showed upper bounds for the Hausdorff distance.
More precisely, they proved that if $K_{n}$ is the convex hull of random
points uniformly distributed on the boundary $\partial K$ of an arbitrary
convex body $K$, then with probability one

$\delta_{H}(K,K_{n})\leq C\Big{(}\frac{\log n}{n}\Big{)}^{\alpha}$

for some constant $C>0$ and all $n\in\mathbb{N}$, where
$\alpha=\frac{1}{d-1}$. The exponent $\frac{1}{d-1}$ can be improved to
$\frac{2}{d-1}$ if the body is smooth in the following sense: at each boundary
point, there is a unique normal and this normal is Lipschitz-continuous on
$\partial K$. The latter includes the case of $C^{3}_{+}$-boundary, see, e.g.,
G. Walther [18, Thm. 1]. In [6], a result for points sampled uniformly inside
$K$ was proven, where $\alpha=\frac{1}{d}$ in general and
$\alpha=\frac{2}{d+1}$ for smooth bodies.

A direct consequence of the convergence in (1) and the bounds in [6] is the
following, which we only state for the case of the uniform distribution on
$\partial K$. We prove it in Section 2.

######  Proposition 1.

Let $K$ be of class $C^{3}_{+}$ and, for $n\in\mathbb{N}$, let $K_{n}$ be the
convex hull of $n$ independent random points uniformly distributed on
$\partial K$. Then

$\lim_{n\to\infty}\left(\frac{n}{\log
n}\right)^{\frac{2}{d-1}}\mathbb{E}[\delta_{H}(K,K_{n})]=c_{K},$

where $c_{K}\in(0,\infty)$ is the limiting constant in (1) for
$h\equiv\mathrm{vol}_{d-1}(\partial K)^{-1}$.

In the case when points are chosen independently and uniformly at random
within a convex body $K\subset\mathbb{R}^{d}$, we are only aware of exact
asymptotic results in dimension two. However, for higher-dimensional smooth
convex bodies there is work in progress due to P. Calka and J. Yukich. H.
Bräker, T. Hsing and N.H. Bingham [4] obtained a formula for the limiting
distribution function for smooth convex bodies $K$ and convex polytopes in
$\mathbb{R}^{2}$. More precisely, let $Q$ be a convex polytope in
$\mathbb{R}^{2}$ with interior angles $\alpha_{1},\dots,\alpha_{M}$, and let
$Q_{n}$ be the convex hull of $n$ points chosen uniformly at random from $Q$.
Then [4, Thm. 3] states that

$\lim_{n\to\infty}\mathbb{P}(\sqrt{n}\delta_{H}(Q,Q_{n})\leq
t)=\prod_{i=1}^{M}(1-p_{i}(t)),\qquad t>0,$

where for $i\in\\{1,\dots,M\\}$

$p_{i}(t)=\left\\{\begin{array}[]{cc}\int_{0}^{\alpha_{i}}h_{i}(t,\alpha){\rm
d}\alpha+\exp\left(-\frac{t^{2}}{2\operatorname{vol}_{2}(Q)}\tan\alpha_{i}\right)&0<\alpha_{i}<\frac{\pi}{2}\\\
\int_{\alpha_{i}-\frac{\pi}{2}}^{\frac{\pi}{2}}h_{i}(t,\alpha){\rm
d}\alpha&\frac{\pi}{2}\leq\alpha_{i}<\pi,\end{array}\right.$ (2)

with

$h_{i}(t,\alpha)=\exp\left(-\frac{t^{2}}{2\operatorname{vol}_{2}(Q)}\left(\tan\alpha+\tan(\alpha_{i}-\alpha)\right)\right)\frac{t^{2}}{2\operatorname{vol}_{2}(Q)}\tan^{2}\alpha.$

Note that the limiting distribution is a product of distribution functions,
one for each vertex. Below, we use tail bounds to show that the convergence in
distribution extends also to convergence in expectation. Let us note that V.E.
Brunel [5] provides concentration inequalities for random polytopes in
Hausdorff distance, but an additional log-factor appears in the resulting
bounds on the expectation.

The only result we could find in the literature on the behavior of
$\mathbb{E}[\delta_{H}(K,K_{n})]$ when $K$ is a polytope is due to I. Bárány
[1], who states that it is “almost trivial” that

$\mathbb{E}[\delta_{H}(K,K_{n})]\asymp n^{-1/d},$

where $\asymp$ denotes the equivalence of the two expressions up to positive
absolute constants. Here, the $n$ points are sampled uniformly inside the
polytope. The case of sampling the points uniformly from the boundary is very
similar and leads to the following asymptotics; for completeness a proof will
be presented below.

######  Proposition 2.

Let $Q\subset\mathbb{R}^{d}$ be a convex polytope and, for each
$n\in\mathbb{N}$, let $Q_{n}$ be the convex hull of $n$ points sampled
independently and uniformly from the boundary of $Q$. Then

$\mathbb{E}[\delta_{H}(Q,Q_{n})]\asymp n^{-1/(d-1)}.$

I. Bárány’s result gives the dependence on the number of chosen points but
nothing is known about the precise asymptotic behavior.

In this paper we consider a polygon $Q$ in $\mathbb{R}^{2}$ and determine the
exact constants in $\mathbb{E}[\delta_{H}(Q,Q_{n})]$ as the number of points
chosen on the boundary $\partial Q$ tends to infinity. We will mainly follow
the approach of [4], which is based on Poisson processes, and provide the
necessary arguments to achieve convergence in expectation.

We now present the main results of this paper. We start with the asymptotic
behavior of the expected Hausdorff distance of a convex polygon and the random
polytope formed by the convex hull of $n$ independent uniform points on the
boundary of this polygon as $n\to\infty$.

######  Theorem 1.

Let $Q$ be a convex polygon with $M\geq 3$ vertices, interior angles
$\alpha_{1},\dots,\alpha_{M}\in(0,\pi)$ and total edge length
$\left|\partial\,Q\right|$. For each $n\in\mathbb{N}_{\geq 3}$, let
$X_{1},\dots,X_{n}$ be independent and uniformly distributed points on the
boundary of $Q$, and $Q_{n}=[X_{1},\dots,X_{n}]$ their convex hull. Then

$\lim_{n\to\infty}n\,\mathbb{E}[\delta_{H}(Q,Q_{n})]=\left|\partial\,Q\right|\int_{0}^{\infty}1-\prod_{i=1}^{M}\Big{(}1-r\int_{\ell_{\alpha_{i}}}^{\infty}e^{-r(y+h(y,\alpha_{i}))}{\rm
d}y\Big{)}{\rm d}r.$ (3)

Here,

$\ell_{\alpha}:=\begin{cases}1&:\,\alpha<\pi/2,\\\
\sin(\alpha)^{-1}&:\,\alpha\geq\pi/2,\end{cases}$ (4)

and

$h(y,\alpha):=y\frac{\sin(\alpha)\sqrt{y^{2}-1}-\cos(\alpha)}{\sin^{2}(\alpha)y^{2}-1}$
(5)

if

$\alpha<\pi/2\text{ and
}y\in[1,\cos(\alpha)^{-1}]\quad\text{or}\quad\alpha\geq\pi/2\text{ and
}y>\sin(\alpha)^{-1}.$

If $\alpha<\pi/2$ and $y>\cos(\alpha)^{-1}$, then we set $h(y,\alpha):=1$.

$r$$\alpha_{i}$$ry$$rh(y,\alpha_{i})$ Figure 1:  The exponent
$r\,h(y,\alpha_{i})$ in Theorem 1 is the length cut off from the boundary
$\partial Q$ by a tangent line to a circle with radius $r$ centered at a
vertex that intersects one edge at distance $ry$ from the vertex and the other
necessarily at distance $rh(y,\alpha_{i})$. For $\alpha_{i}<\pi/2$ and
$y>\cos(\alpha_{i})^{-1}$ the picture is different, see Figure 2 below.
$\alpha_{i}$$ry$$r$$r\cos(\alpha_{i})^{-1}$ Figure 2: In the case
$\alpha_{i}\in(0,\pi/2)$, tangents to the circle with radius $r$ centered at a
vertex which intersect one edge at distance greater than
$r\cos(\alpha_{i})^{-1}$ from the vertex intersect the other edge at distance
$r$.

In order to determine the dependence on the interior angles of the polygon, we
deduce the following asymptotics from Theorem 1 in the case when all angles
are greater than $\frac{\pi}{2}$.

######  Corollary 3.

If $Q$ and $Q_{n}$ are as in Theorem 1 (i.e., $M\geq 3$) and
$\alpha_{1},\dots,\alpha_{M}\geq\pi/2$, we have

$\frac{1}{5}A(Q)\leq\lim_{n\to\infty}n\,\mathbb{E}[\delta_{H}(Q,Q_{n})]\leq
A(Q),$

where

$A(Q):=\left|\partial\,Q\right|\sum_{k=1}^{M}(-1)^{k+1}\sum_{1\leq
i_{1}<\cdots<i_{k}\leq
M}\frac{1}{\frac{1}{\sin\alpha_{i_{1}}}+\cdots+\frac{1}{\sin\alpha_{i_{k}}}}.$

In the case when all angles are equal, $Q$ is a regular polygon and we obtain
the following asymptotics.

######  Corollary 4.

Let $Q_{M}^{\rm reg}$ be a regular polygon with $M\geq 4$ vertices and
$Q_{M,n}$ the convex hull of $n$ points independently and uniformly sampled
from the boundary of $Q_{M}^{\rm reg}$. Then

$\lim_{n\to\infty}n\,\mathbb{E}[\delta_{H}(Q_{M}^{\rm
reg},Q_{M,n})]\asymp\left|\partial Q_{M}^{\rm reg}\right|\,\frac{\log M}{M}.$

###### Proof.

Let $\beta$ be the exterior angle of $Q_{M}^{\rm reg}$. Then
$\beta=\frac{2\pi}{M}$ and thus
$\alpha=\pi-\beta=\pi(1-\frac{2}{M})\geq\frac{\pi}{2}$, as $M\geq 4$. Hence we
can apply Corollary 3. Corollary 3 yields for a regular $M$-gon that
$\lim_{n\to\infty}n\,\mathbb{E}[\delta_{H}(Q,Q_{n})]$ is up to absolute
constants equal to

$\displaystyle\sum_{k=1}^{M}(-1)^{k+1}\sum_{1\leq i_{1},\cdots i_{k}\leq
M}\frac{1}{\frac{1}{\sin\alpha_{i_{1}}}+\cdots+\frac{1}{\sin\alpha_{i_{k}}}}=\sum_{k=1}^{M}(-1)^{k+1}{M\choose
k}\frac{\sin\alpha_{M}}{k},$

where

$\sin(\alpha_{M})=\sin(\pi(1-2/M))\asymp\frac{2\pi}{M}.$

By formula [8, 0.155/4], it holds that

$\sum_{k=1}^{M}\binom{M}{k}(-1)^{k+1}\frac{1}{k}=\sum_{k=1}^{M}\frac{1}{k}\asymp\log
M,$

which completes the proof. ∎

We conclude this section with a remark on the log-factor in Corollary 4 and a
remark on higher moments.

######  Remark 1.

The logarithm appearing in Corollary 4 can be heuristically derived from the
asymptotic independence of the random variables

$Z_{i}:=n\,\mathrm{dist}(v_{i},K_{n}),\quad i\in\\{1,\dots,M\\},$

which is crucial in the proof of Theorem 1 below. Assuming that these random
variables are in fact independent, we can use Lemma 5 below to write

$n\,\mathbb{E}[\delta_{H}(Q_{M}^{\rm
reg},Q_{M,n})]=\mathbb{E}\big{[}\max_{1\leq i\leq M}Z_{i}\big{]}$

as a maximum of independent random variables. Bounds appearing in the proof of
Corollary 3 allow us to conclude that the tails $\mathbb{P}(M\cdot Z_{i}\geq
r)$ decay exponentially in $r$. This yields that
$M\mathbb{E}\big{(}\max_{1\leq i\leq M}Z_{i}\big{)}$ is of order $\log M$,
which is the statement of Corollary 4. To give an idea for this implication,
note that by a substitution we have

$\displaystyle M\,\mathbb{E}\Big{[}\max_{1\leq i\leq M}Z_{i}\Big{]}$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}\Big{(}\max_{1\leq i\leq M}Z_{i}\geq
r/M\Big{)}{\rm d}r$ $\displaystyle=(\log
M)\int_{0}^{\infty}1-\prod_{i=1}^{M}\big{(}1-\mathbb{P}(M\cdot Z_{i}\geq x\log
M)\big{)}{\rm d}x,$

and we can insert the tail bounds to derive the stated asymptotics.

######  Remark 2.

We can also establish asymptotics for arbitrary moments. Let $\gamma>0$ be a
real number. Modifying the first steps of the proof of Theorem 1 and using
that

$\mathbb{E}[\delta_{H}(Q,Q_{n})^{\gamma}]=\gamma\int_{0}^{\infty}r^{\gamma-1}\mathbb{P}(\delta_{H}(Q,Q_{n})\geq
r){\rm d}r$

will give, with the notation of Theorem 1, that

$\lim_{n\to\infty}n^{\gamma}\mathbb{E}[\delta_{H}(Q,Q_{n})^{\gamma}]=\gamma\,\left|\partial\,Q\right|^{\gamma}\int_{0}^{\infty}r^{\gamma-1}\Bigg{(}1-\prod_{i=1}^{M}\Big{(}1-r\int_{\ell_{\alpha_{i}}}^{\infty}e^{-r(y+h(y,\alpha_{i}))}{\rm
d}y\Big{)}\Bigg{)}{\rm d}r.$

We conclude this section by introducing notation and relevant notions. We then
present the proofs of our results in Section 2.

Notation.  The Euclidean ball with center $x\in\mathbb{R}^{d}$ and radius
$\rho>0$ is denoted by $B_{2}^{d}(x,\rho)$. We write in short
$B_{2}^{d}:=B_{2}^{d}(0,1)$ for the unit ball. For a set $A$, its
$d$-dimensional Hausdorff measure or volume is $\mathrm{vol}_{d}(A)$ or $|A|$,
its diameter is $\mathrm{diam}(A)$. The distance of the set $A$ to another set
$B$ is $\mathrm{dist}(A,B)=\inf\\{\|x-y\|:x\in A,y\in B\\}$. In particular,
$\mathrm{dist}(x,K)=\inf_{y\in K}\|x-y\|$.

The symmetric difference metric between two convex bodies $C$ and $K$, i.e.,
compact, convex subsets of $\mathbb{R}^{d}$ with nonempty interior, is

$d_{S}(C,K)=\operatorname{vol}_{d}(C\setminus
K)+\operatorname{vol}_{d}(K\setminus C)$

and the Hausdorff metric between two convex bodies $C$ and $K$ is

$\delta_{H}(C,K)=\inf\\{\rho\geq 0\colon C\subseteq K+B_{2}^{d}(0,\rho)\hskip
2.84526pt\mbox{and}\hskip 2.84526ptK\subseteq C+B_{2}^{d}(0,\rho)\\},$

where $C+K=\\{x+y\colon x\in C\hskip 2.84526pt\mbox{and}\hskip 2.84526pty\in
K\\}$ is their Minkowski sum. The convex hull of points
$x_{1},\dots,x_{n}\in\mathbb{R}^{d}$ is a convex polytope denoted by
$[x_{1},\dots,x_{n}]$.

##  2 Proofs

We first give the proof of Theorem 1, deduce Corollary 3, and then prove
Propositions 1 and 2. To do so, we need additional lemmas.

An important observation is the fact that for a convex polytope the Hausdorff
distance to a convex subset is attained at the vertices and asymptotically, as
$n\to\infty$, “everything happens at the vertices”.

######  Lemma 5.

Let $d\geq 2$. Let $M\in\mathbb{N}$ and let $Q\subset\mathbb{R}^{d}$ be a
convex polytope with vertices $v_{1},\dots,v_{M}$. If $K\subset Q$ is a
convex, nonempty subset, then

$\delta_{H}(Q,K)=\max_{1\leq i\leq M}\mathrm{dist}(v_{i},K).$

This lemma is known, see, e.g., [5, Lem. 2], and follows from the fact that
the convex continuous function $\mathrm{dist}(\cdot,K)$ attains its maximum on
$Q$ at a vertex.

The following lemma will be useful for geometric computations.

######  Lemma 6.

Let $D$ be a triangle in $\mathbb{R}^{2}$ with sides of lengths $a,b,c$ and
angle $\alpha\in(0,\pi)$ between the sides $b$ and $c$. Then the height $h$
with respect to the side $a$ equals

$h=\frac{bc\sin\alpha}{\sqrt{b^{2}+c^{2}-2bc\cos\alpha}}.$ (6)

###### Proof.

Formula (6) follows from elementary trigonometry. The area $|D|$ of $D$ equals

$\frac{1}{2}a\cdot h=|D|=\frac{1}{2}bc\sin\alpha.$

Using the law of cosine, $a^{2}=b^{2}+c^{2}-2bc\cos\alpha$, we obtain

$h=\frac{bc}{a}\sin\alpha=\frac{bc\sin\alpha}{\sqrt{b^{2}+c^{2}-2bc\cos\alpha}},$

which proves the desired formula. ∎

As a consequence of Lemma 6 we deduce the function $h$ in Theorem 1.

######  Lemma 7.

Let $C$ be the cone in $\mathbb{R}^{2}$ spanned by vectors
$u,v\in\mathbb{R}^{2}$ of unit length and enclosing an angle
$\alpha\in(0,\pi)$. For any $r>0$, the tangent line to $B_{2}^{2}(0,r)\cap C$
which intersects one edge in $tu$, where $t\geq r$, passes through
$rh(t/r,\alpha)v$, where $h$ is as in Theorem 1.

###### Proof.

Let $F_{u}=\\{tu\colon t\geq 0\\}$ and $F_{v}=\\{tv\colon t\geq 0\\}$ and let
$T$ be the tangent to $B_{2}^{2}(0,r)\cap C$ which intersects $F_{u}$ in the
point $tu$, $t>0$. Let $s(t)v$ be the point where $T$ intersects $F_{v}$,
$s(t)>0$.

In the case $\pi/2\leq\alpha<\pi$, Lemma 6 implies that the triangle formed by
the origin, $tu$ and $s(t)v$ has height

$r=\frac{ts(t)\sin\alpha}{\sqrt{t^{2}+s(t)^{2}-2ts(t)\cos\alpha}}.$

Solving for $s(t)$, we get

$s(t)=r\,t\frac{\sin\alpha\sqrt{t^{2}-r^{2}}-r\cos\alpha}{t^{2}\sin^{2}\alpha-r^{2}}=rh(t/r,\alpha),$
(7)

Let now $0<\alpha<\pi/2$. If $t<r\cos(\alpha)^{-1}$, then, again by Lemma 6,
$s(t)$ is as in (7). If $t\geq r\cos(\alpha)^{-1}$, then
$s(t)=r=rh(t/r,\alpha)$. ∎

Now we can prove Theorem 1.

###### Proof of Theorem 1.

After a possible rescaling we can assume that $|\partial Q|=1$. We adapt the
proof of [4, Thm. 3] in order to first prove the distributional convergence

$\lim_{n\to\infty}\mathbb{P}(n\delta_{H}(Q,Q_{n})\leq
r)=\prod_{i=1}^{M}(1-q_{i}(r)),\quad r>0,$ (8)

where

$q_{i}\colon\mathbb{R}_{+}\to\mathbb{R}_{+},\quad r\mapsto
r\int_{\ell_{\alpha_{i}}}^{\infty}e^{-r(y+h(y,\alpha_{i}))}{\rm d}y,$

with $\ell_{\alpha}$ and $h(y,\alpha)$ as in Theorem 1. Recall that $Q_{n}$ is
the convex hull of $n$ independently and uniformly distributed points
$X_{1},\dots,X_{n}$ on $\partial Q$.

First, we show how (8) implies the convergence in expectation which is claimed
in Theorem 1. We have the tail bound (see also the proof of (17) of
Proposition 2)

$\displaystyle\mathbb{P}(n\delta_{H}(Q,Q_{n})>r)$
$\displaystyle\leq\sum_{i=1}^{M}\mathbb{P}(n\mathrm{dist}(v_{i},Q_{n})>r)$
$\displaystyle\leq\sum_{i=1}^{M}\mathbb{P}(\\{X_{1},\dots,X_{n}\\}\cap
B_{2}^{2}(v_{i},r/n)=\emptyset)$ $\displaystyle\leq Me^{-cr},\quad
n\in\mathbb{N},$

where $c=2/|\partial Q|$. Thus, for $p>1$,

$\sup_{n\in\mathbb{N}}\mathbb{E}[n\delta_{H}(Q,Q_{n})]^{p}=\sup_{n\in\mathbb{N}}\int_{0}^{\infty}\mathbb{P}(n\delta_{H}(Q,Q_{n})\geq
r^{1/p}){\rm d}r\leq M\int_{0}^{\infty}e^{-cr^{1/p}}{\rm d}r<\infty,$

i.e., the sequence $(n\delta_{H}(Q,Q_{n}))_{n\in\mathbb{N}}$ is uniformly
integrable and

$\lim_{n\to\infty}n\mathbb{E}[\delta_{H}(Q,Q_{n})]=\int_{0}^{\infty}1-\prod_{i=1}^{M}(1-q_{i}(r)){\rm
d}r.$

This extends to arbitrary moments.

We show (8), following [4]. We refer to [9] for more information on (Poisson)
point processes. We begin with some preparation. Let

$L=\frac{\min_{1\leq i\leq M}\|v_{i}-v_{i+1}\|_{2}}{2},$

where we set $v_{M+1}=v_{1}$. Then the ball $B_{2}^{2}(v_{i},L),1\leq i\leq
M,$ only intersects the edges of $Q$ which are incident to $v_{i}$.

For $1\leq i\leq M$, define the point process
$\xi_{n,i}=\sum_{j=1}^{n}\delta_{n(X_{j}-v_{i})\cap B_{2}^{2}(0,Ln)}$ regarded
as a random element in the space $\mathcal{N}_{i}$ of locally finite counting
measures on the boundary of a cone $C_{i}$ with apex at the origin and angle
$\alpha_{i}$. When $1\leq i\leq M$, we can write $C_{i}$ as the convex hull of
two rays spanned by unit vectors $a_{i},b_{i}\in\mathbb{R}^{2}$. We endow
$\mathcal{N}_{i}$, $1\leq i\leq M$, with the vague topology and Borel
$\sigma$-field.

As $n\to\infty$, we have

$(\xi_{n,1},\dots,\xi_{n,M})\xrightarrow[n\to\infty]{\rm
d}(\xi_{1},\dots,\xi_{M}),$ (9)

where $\xi_{1},\dots,\xi_{M}$ are independent Poisson processes on $\partial
C_{1},\dots,\partial C_{M}$, respectively, and intensity measure being
Lebesgue measure. Thus, for every Borel subset $B\subset\partial C_{i}$, the
distribution of the number of points $\xi_{i}(B)$ of $\xi_{i}$ in $B$ is a
Poisson random variable with parameter $|B|$, and for any choice of disjoint
Borel sets $B_{1},\dots,B_{m}\subset\partial C_{i}$ the random variables
$\xi_{i}(B_{1}),\dots,\xi_{i}(B_{m})$ are independent. Moreover, these are
independent from $\xi_{j}(A_{1}),\dots,\xi_{j}(A_{m})$, whenever
$A_{1},\dots,A_{m}\subset\partial C_{j}$ are disjoint and $i\neq j$.

For convenience of readers unfamiliar with Poisson processes, we provide a
brief justification of (9). Choose bounded measurable sets
$A_{i}\subset\partial C_{i}$ and integers $k_{i}\in\mathbb{N}_{0}$ for each
$i$. Then (9) is equivalent to

$\lim_{n\to\infty}\mathbb{P}(\xi_{n,1}(A_{1})=k_{1},\dots,\xi_{n,M}(A_{M})=k_{M})=\prod_{i=1}^{M}\mathbb{P}(\xi_{i}(A_{i})=k_{i}),$
(10)

where $\xi_{i}(A_{i})$ is Poisson distributed with parameter $|A_{i}|$. For
$n$ large enough such that the sets $v_{i}+\frac{1}{n}A_{i},i=1,\dots,M,$ are
disjoint and part of the polygon $Q$ which has $|\partial Q|=1$, and
$\sum_{i=1}^{M}k_{i}<n$, we compute

$\displaystyle\mathbb{P}(|\\{j\colon X_{j}\in
v_{1}+\frac{1}{n}A_{1}\\}|=k_{1},\dots,|\\{j\colon X_{j}\in
v_{M}+\frac{1}{n}A_{M}\\}|=k_{M})$ $\displaystyle=\frac{n!}{k_{1}!\cdots
k_{M}!(n-\sum_{i=1}^{M}k_{i})!}\Big{(}\frac{|A_{1}|}{n}\Big{)}^{k_{1}}\cdots\Big{(}\frac{|A_{M}|}{n}\Big{)}^{k_{M}}\Big{(}1-\frac{\sum_{i=1}^{M}|A_{i}|}{n}\Big{)}^{n-\sum_{i=1}^{M}k_{i}}.$

Taking the limit, we arrive at

$\lim_{n\to\infty}\mathbb{P}(\xi_{n,1}(A_{1})=k_{1},\dots,\xi_{n,M}(A_{M})=k_{M})=\frac{1}{k_{1}!\cdots
k_{M}!}|A_{1}|^{k_{1}}\cdots|A_{M}|^{k_{M}}e^{-\sum_{i=1}^{M}|A_{i}|}.$

This proves (10), and thus (9).

We continue the proof of Theorem 1. By Lemma 5 we have

$n\,\delta_{H}(Q,Q_{n})=\max_{1\leq i\leq M}n\,\mathrm{dist}(v_{i},Q_{n}).$
(11)

Provided that for all $1\leq i\leq M$ the point process $\xi_{n,i}$ has
nonempty intersection with both rays forming $\partial C_{i}$, we have

$n\,\delta_{H}(Q,Q_{n})=\max_{1\leq i\leq
M}n\,\mathrm{dist}(v_{i},Q_{n})=\max_{1\leq i\leq M}f_{i}(\xi_{n,i}),$

where $f_{i}$ continuously maps any locally finite counting measure
$\eta\in\mathcal{N}_{i}$ to the smallest distance between the origin and the
convex hull of the points of $\eta$. In fact, the probability that for some
$1\leq i\leq M$ the process $\xi_{n,i}$ does not intersect one of the rays
forming $\partial C_{i}$ is given by

$\mathbb{P}(\exists i\colon X_{j}\not\in[v_{i},v_{i}+La_{i}]\text{ for all
}j=1,\dots,n\lor X_{j}\not\in[v_{i},v_{i}+Lb_{i}]\text{ for all
}j=1,\dots,n),$

which, by a union bound, is bounded by $2M(1-L)^{n}$ as $|\partial Q|=1$.
Therefore,

$\mathbb{P}(n\,\delta_{H}(Q,Q_{n})\neq\max_{1\leq i\leq
M}f_{i}(\xi_{n,i}))\leq 2M(1-L)^{n}\to 0.$ (12)

By the continuous mapping theorem it follows from (9) that

$\max_{1\leq i\leq M}f_{i}(\xi_{n,i})\xrightarrow[n\to\infty]{\rm
d}\max_{1\leq i\leq M}f_{i}(\xi_{i}).$

Combined with 11, we get

$n\delta_{H}(Q,Q_{n})\xrightarrow[n\to\infty]{\rm d}\max_{1\leq i\leq
M}f_{i}(\xi_{i}).$

If we can show that, for $i=1,\dots,M$,

$\mathbb{P}(f_{i}(\xi_{i})>r)=q_{i}(r),\quad r>0,$ (13)

then

$\lim_{n\to\infty}\mathbb{P}(n\delta_{H}(Q,Q_{n})\leq
r)=\mathbb{P}(\max_{1\leq i\leq M}f_{i}(\xi_{i})\leq
r)=\prod_{i=1}^{M}(1-q_{i}(r)),$

i.e., (8) and thus the conclusion holds.

We show (13) for $1\leq i\leq M$ and $r>0$. Define the random variable
$T_{i}=\inf\\{y>0\colon\xi_{i}([0,ya_{i}])\neq 0\\}$, i.e., the distance to
the origin of the closest point to the origin belonging to $\xi_{i}$ and being
on one ray of $\partial C_{i}$.

Observe that for any $R>0$, by the law of total probability and Lemma 7,

$\displaystyle\mathbb{P}(f_{i}(\xi_{i})>r,T_{i}\leq R)$
$\displaystyle=\int_{0}^{R}\mathbb{P}(f_{i}(\xi_{i})>r|T_{i}=y){\rm
d}\mathbb{P}(T_{i}\leq y)$
$\displaystyle=\int_{\ell_{\alpha_{i}}r}^{R}\mathbb{P}(\xi_{i}([0,rh(y/r,\alpha_{i})a_{i}])=0){\rm
d}\mathbb{P}(T_{i}\leq y)$
$\displaystyle=\int_{\ell_{\alpha_{i}}r}^{R}e^{-rh(y/r,\alpha_{i})-y}{\rm
d}y,$

since $\mathbb{P}(f_{i}(\xi_{i})>r|T_{i}=y)$ is the probability that the
points of $\xi_{i}$ can be separated from the origin by a line passing through
$ya_{i}$ and having distance $r$ from the origin, conditional on the fact that
one point lies in $ya_{i}$. Further, note that the distribution of $T_{i}$ has
Lebesgue density

$\frac{\partial}{\partial y}\mathbb{P}(T_{i}\leq y)=\frac{\partial}{\partial
y}\mathbb{P}(\xi_{i}([0,ya_{i}])\neq 0)=\frac{\partial}{\partial
y}(1-\mathbb{P}(\xi_{i}([0,ya_{i}])=0))=e^{-y},\quad y>0.$

Letting $R\to\infty$ gives

$\mathbb{P}(f_{i}(\xi_{i})>r)=\lim_{R\to\infty}\mathbb{P}(f_{i}(\xi_{i})>r,T_{i}\leq
R)=\int_{\ell_{\alpha_{i}}r}^{\infty}e^{-rh(y/r,\alpha_{i})-y}{\rm
d}y=q_{i}(r).$

This completes the proof.

∎

######  Remark 3.

Note that a similar approach as in the proof of Theorem 1 can be used to show
the convergence in expectation

$\lim_{n\to\infty}\sqrt{n}\mathbb{E}[\delta_{H}(Q,Q_{n})]=\int_{0}^{\infty}1-\prod_{i=1}^{M}(1-p_{i}(r)){\rm
d}r,$

where $Q_{n}$ is the convex hull of $n$ independent random points distributed
uniformly inside $Q$ and $p_{i}$ is as in (2).

###### Proof of Corollary 3.

With notation as in Theorem 1, it holds by (3) that

$\displaystyle\lim_{n\to\infty}n\,\mathbb{E}[\delta_{H}(Q,Q_{n})]=\left|\partial\,Q\right|\int_{0}^{\infty}1-\prod_{i=1}^{M}\Big{(}1-r\int_{\ell_{\alpha_{i}}}^{\infty}e^{-r(y+h(y,\alpha_{i}))}{\rm
d}y\Big{)}{\rm d}r.$

As by assumption $\alpha_{i}\geq\frac{\pi}{2}$ for all $i$, we have that
$\ell_{\alpha_{i}}=\frac{1}{\sin\alpha_{i}}$ for all $1\leq i\leq M$. Since
the function $h\geq 0$, for all $1\leq i\leq M$,

$r\int_{\ell_{\alpha_{i}}}^{\infty}e^{-r(y+h(y,\alpha_{i}))}{\rm d}y\leq
r\int_{\ell_{\alpha_{i}}}^{\infty}e^{-r\cdot y}{\rm
d}y=e^{-r\cdot\ell_{\alpha_{i}}},$

and hence

$\displaystyle\prod_{i=1}^{M}\Big{(}1-r\int_{\ell_{\alpha_{i}}}^{\infty}e^{-r(y+h(y,\alpha_{i}))}{\rm
d}y\Big{)}\geq\prod_{i=1}^{M}\big{(}1-e^{-r\cdot\ell_{\alpha_{i}}}\big{)}$
$\displaystyle=1-\left(\sum_{k=1}^{M}(-1)^{k+1}\sum_{1\leq
i_{1}<\cdots<i_{k}\leq
M}\exp(-r(\ell_{\alpha_{i_{1}}}+\cdots+\ell_{\alpha_{i_{k}}}))\right).$

Since $\ell_{\alpha_{i}}=\frac{1}{\sin\alpha_{i}}$ for all $i=1,\dots,M$, we
have

$\displaystyle\lim_{n\to\infty}n\,\mathbb{E}[\delta_{H}(Q,Q_{n})]$
$\displaystyle\leq\left|\partial\,Q\right|\int_{0}^{\infty}\left(\sum_{k=1}^{M}(-1)^{k+1}\sum_{1\leq
i_{1}<\cdots<i_{k}\leq
M}\exp(-r(\ell_{\alpha_{i_{1}}}+\cdots+\ell_{\alpha_{i_{k}}}))\right){\rm d}r$
$\displaystyle=\left|\partial\,Q\right|\sum_{k=1}^{M}(-1)^{k+1}\sum_{1\leq
i_{1}<\cdots<i_{k}\leq
M}\frac{1}{\ell_{\alpha_{i_{1}}}+\cdots+\ell_{\alpha_{i_{k}}}}$
$\displaystyle=\left|\partial\,Q\right|\sum_{k=1}^{M}(-1)^{k+1}\sum_{1\leq
i_{1}<\cdots<i_{k}\leq
M}\frac{1}{\frac{1}{\sin\alpha_{i_{1}}}+\cdots+\frac{1}{\sin\alpha_{i_{k}}}}.$

Now we treat the inverse inequality. For $y\geq\frac{2}{\sin\alpha}$ we have,
for any $\alpha\geq\frac{\pi}{2}$,

$\frac{y^{2}}{2}\sin^{2}\alpha\leq y^{2}\sin^{2}\alpha-1.$

Therefore,

$\displaystyle
h(y,\alpha)=y\frac{\sin(\alpha)\sqrt{y^{2}-1}-\cos(\alpha)}{y^{2}\sin^{2}(\alpha)-1}\leq
y\frac{\sin(\alpha)y-\cos\alpha}{y^{2}\sin^{2}(\alpha)-1}\leq\frac{2}{\sin\alpha}-\frac{2\cos\alpha}{y\sin^{2}\alpha}\leq\frac{3}{\sin\alpha}.$

It follows that

$r\int_{\ell_{\alpha}}^{\infty}e^{-r(y+h(y,\alpha))}{\rm d}y\geq
r\int_{2\ell_{\alpha}}^{\infty}e^{-r(y+\frac{3}{\sin\alpha})}{\rm
d}y=re^{-r\frac{3}{\sin\alpha}}\int_{2\ell_{\alpha}}^{\infty}e^{-ry}{\rm
d}y=e^{-r\frac{5}{\sin\alpha}}.$

We complete the proof with

$\displaystyle\lim_{n\to\infty}n\,\mathbb{E}[\delta_{H}(Q,Q_{n})]=\left|\partial\,Q\right|\int_{0}^{\infty}1-\prod_{i=1}^{M}\big{(}1-r\int_{\ell_{\alpha_{i}}}^{\infty}e^{-r(y+h(y,\alpha_{i}))}{\rm
d}y\big{)}{\rm d}r$
$\displaystyle\geq\left|\partial\,Q\right|\int_{0}^{\infty}1-\prod_{i=1}^{M}\big{(}1-e^{-r\frac{5}{\sin\alpha_{i}}}\big{)}{\rm
d}r$
$\displaystyle=\left|\partial\,Q\right|\int_{0}^{\infty}\left(\sum_{k=1}^{M}(-1)^{k+1}\sum_{1\leq
i_{1}<\cdots<i_{k}\leq
M}\exp\left(-5r\left(\frac{1}{\sin\alpha_{i_{1}}}+\cdots+\frac{1}{\sin\alpha_{i_{k}}}\right)\right)\right){\rm
d}r$
$\displaystyle=\frac{1}{5}\left|\partial\,Q\right|\left(\sum_{k=1}^{M}(-1)^{k+1}\sum_{1\leq
i_{1}<\cdots<i_{k}\leq
M}\frac{1}{\frac{1}{\sin\alpha_{i_{1}}}+\cdots+\frac{1}{\sin\alpha_{i_{k}}}}\right).$

∎

###### Proof of Proposition 1.

Define for $n\in\mathbb{N}$ the random variable

$X_{n}=\Big{(}\frac{n}{\log n}\Big{)}^{2/(d-1)}\delta_{H}(K,K_{n}).$

We deduce from tail bounds given in [6] that
$X_{n}\xrightarrow{\mathbb{P}}c_{K}$ implies $\mathbb{E}[X_{n}]\to c_{K}$.

As $K$ is $C^{3}_{+}$, there is in particular at each boundary point
$x\in\partial K$ a unique normal $N(x)$ and there exists $\ell>0$ such that
$|N(x)-N(y)|\leq\ell|x-y|$ for all $x,y\in\partial K$, see [6]. Then, for
$w>0$ and $n\in\mathbb{N}$,

$\mathbb{P}(X_{n}>\ell\,w)=\mathbb{P}\Big{(}\delta_{H}(K,K_{n})>\ell\,w\Big{(}\frac{\log
n}{n}\Big{)}^{2/(d-1)}\Big{)}=\mathbb{P}(\delta_{H}(K,K_{n})>\ell\delta_{n}^{2}),$

where we set $\delta_{n}=\sqrt{w}\Big{(}\frac{\log n}{n}\Big{)}^{1/(d-1)}$.
Thus, by [6, Thm. 1(b)], we have

$\mathbb{P}(X_{n}>\ell\,w)\leq\mathbb{P}(\partial K\not\subset
B(Z_{n},\delta_{n})),$

where $Z_{n}=\\{X_{1},\dots,X_{n}\\}$ and
$B(Z_{n},\delta_{n})=\bigcup_{i=1}^{n}B_{2}^{2}(X_{i},\delta_{n})$ is a union
of random Euclidean balls. From the proof of [6, Lem. 1], we get

$\mathbb{P}(\partial K\not\subset
B(Z_{n},\delta_{n}))\leq(4R+\alpha)^{d}(\delta_{n}/2)^{-d}\exp(-\alpha
n(\delta_{n}/2)^{d-1})$

for some constants $R,\alpha>0$ and both, $w$ and $n$ sufficiently large. This
yields $c,C>0$ independent of $w$ and $n$ such that

$\mathbb{P}(X_{n}\geq\ell\,w)\leq Cw^{-d/2}\Big{(}\frac{n}{\log
n}\Big{)}^{d/(d-1)}\exp(-cw^{(d-1)/2}\log n).$ (14)

Pick $S>\max\\{c_{K},\ell\\}$. Then

$\mathbb{E}[X_{n}]=\int_{0}^{\infty}\mathbb{P}(X_{n}\geq w){\rm
d}w=\int_{0}^{S}\mathbb{P}(X_{n}\geq w){\rm
d}w+\ell^{-1}\int_{S\,\ell^{-1}}^{\infty}\mathbb{P}(X_{n}>\ell\,w){\rm d}w.$
(15)

Since $X_{n}\xrightarrow{\mathbb{P}}c_{K}$, by the Dominated Convergence
theorem, the first summand satisfies

$\int_{0}^{S}\mathbb{P}(X_{n}\geq w){\rm
d}w\to\int_{0}^{S}\mathbb{P}(c_{K}\geq w){\rm d}w=c_{K}.$

Using (14), we will show that the second summand in (15) tends to zero. It
satisfies

$\ell^{-1}\int_{S\,\ell^{-1}}^{\infty}\mathbb{P}(X_{n}>\ell\,w){\rm d}w\leq
C\Big{(}\frac{n}{\log
n}\Big{)}^{d/(d-1)}\ell^{-1}\int_{S\,\ell^{-1}}^{\infty}w^{-d/2}\exp(-cw^{(d-1)/2}\log
n){\rm d}w.$

Since $L:=S\,\ell^{-1}>1$, we estimate the integral from above using
$w^{-d/2}\leq 1$ for $w\geq L$. Then it remains to bound, for
$\alpha=\frac{d-1}{2}$ and $c_{n}=c\log n$,

$\int_{L}^{\infty}e^{-c_{n}w^{\alpha}}{\rm
d}w=c_{n}^{-1/\alpha}\int_{c_{n}^{1/\alpha}L}^{\infty}e^{-w^{\alpha}}{\rm
d}w.$

The tail bound

$\int_{t}^{\infty}e^{-u^{\alpha}}{\rm
d}u\leq\int_{t}^{\infty}\frac{u^{\alpha-1}}{t^{\alpha-1}}e^{-u^{\alpha}}{\rm
d}u=\frac{e^{-t^{\alpha}}}{\alpha t^{\alpha-1}},\quad t>0,$

gives

$\int_{L}^{\infty}e^{-c_{n}w^{\alpha}}{\rm d}w\lesssim n^{-cL^{\alpha}},$

which goes to zero faster than any fixed polynomial if $S$ is chosen large
enough. Thus, the second summand in (15) tends to zero and the proof is
complete.

∎

###### Proof of Proposition 2.

Let $v_{1},\dots,v_{M}$ be the vertices of $Q$ and
$Q_{n}=[X_{1},\dots,X_{n}]$, where $X_{1},\dots,X_{n}$ are sampled
independently at random from $\partial Q$. Then Lemma 5 implies

$n^{1/(d-1)}\mathbb{E}[\delta_{H}(Q,Q_{n})]=\int_{0}^{\infty}\mathbb{P}\big{(}\max_{1\leq
i\leq M}\mathrm{dist}(v_{i},Q_{n})\geq rn^{-1/(d-1)}\big{)}{\rm d}r,\quad
n\in\mathbb{N}.$

Let $n\in\mathbb{N}$ and $r>0$. If $rn^{-1/(d-1)}\geq\mathrm{diam}(Q)$ the
integrand vanishes. Otherwise, a union bound gives

$\mathbb{P}\big{(}\max_{1\leq i\leq M}\mathrm{dist}(v_{i},Q_{n})\geq
rn^{-1/(d-1)}\big{)}\leq\sum_{i=1}^{M}\mathbb{P}(\mathrm{dist}(v_{i},Q_{n})\geq
rn^{-1/(d-1)}).$

For all $i=1,\dots,M$, if $\mathrm{dist}(v_{i},Q_{n})\geq rn^{-1/(d-1)}$, then

$B^{2}_{2}(v_{i},rn^{-1/(d-1)})\cap\\{X_{1},\dots,X_{n}\\}=\emptyset.$

Further, there exists a constant $c=c(Q)\in(0,\infty)$ such that, for all
$i=1,\dots,M$ and for all $\varrho\in(0,\mathrm{diam}(Q)]$,

$\mathbb{P}(X_{1}\in B^{2}_{2}(v_{i},\varrho))\geq c\,\varrho^{d-1}.$ (16)

Therefore, for all $i=1,\dots,M$,

$\mathbb{P}\big{(}\mathrm{dist}(v_{i},Q_{n})\geq
rn^{-1/(d-1)}\big{)}\leq(1-cr^{d-1}/n)^{n}\leq e^{-cr^{d-1}}.$ (17)

Summing over $i=1,\dots,M$ and integrating over $r\in(0,\infty)$ gives an
upper bound, independent of $n$, on the quantity
$n^{1/(d-1)}\mathbb{E}[\delta_{H}(Q,Q_{n})]$.

For the lower bound we note that for every $i=1,\dots,M$ there exists
$c_{i}\in(0,\infty)$ such that for all $\varrho>0$ and all point sets
$\\{x_{1},\dots,x_{n}\\}\subset\partial Q$, we have

$B^{2}_{2}(v_{i},c_{i}\varrho)\cap\\{x_{1},\dots,x_{n}\\}=\emptyset\quad\Rightarrow\quad\mathrm{dist}(v_{i},[x_{1},\dots,x_{n}])\geq\varrho.$
(18)

Before we prove this relation, we use it to complete the proof of the lower
bound. Let $C=\max_{1\leq i\leq M}c_{i}$ and let $R>0$ be small enough such
that the balls $B^{2}_{2}(v_{i},C\,R),1\leq i\leq M,$ are pairwise disjoint.
Let $r\in(0,R]$. Then (18) implies that, for all $n\in\mathbb{N}$,

$\displaystyle\mathbb{P}(\delta_{H}(Q,Q_{n})\geq rn^{-1/(d-1)})$
$\displaystyle\geq\mathbb{P}(\\{X_{1},\dots,X_{n}\\}\cap\bigcup_{i=1}^{M}B^{2}_{2}(v_{i},C\,r\,n^{-1/(d-1)})=\emptyset)$
$\displaystyle=(1-c\,C^{d-1}r^{d-1}/n)^{n},$

which is at least $\frac{1}{2}$ provided that $R$ is small enough. Then we
have, for all $n\in\mathbb{N}$,

$n^{1/(d-1)}\mathbb{E}[\delta_{H}(Q,Q_{n})]\geq\int_{0}^{R}\mathbb{P}(\delta_{H}(Q,Q_{n})\geq
rn^{-1/(d-1)}){\rm d}r\geq R/2.$

This completes the lower bound since $R$ depends only on $C$ and thus only on
$Q$.

It remains to show (18). Fix $1\leq i\leq M$ and $\varrho>0$. We will find
$c_{i}>0$ such that for any point set $\\{x_{1},\dots,x_{n}\\}\subset\partial
Q$ with $B^{2}_{2}(v_{i},\varrho)\cap\\{x_{1},\dots,x_{n}\\}=\emptyset$, we
have

$\mathrm{dist}(v_{i},[x_{1},\dots,x_{n}])\geq c_{i}^{-1}\varrho.$

The distance $\mathrm{dist}(v_{i},[x_{1},\dots,x_{n}])$ becomes minimal if
$A=\\{x_{1},\dots,x_{n}\\}\cap\partial B^{2}_{2}(v_{i},\varrho)$ contains at
least two points, say $x$ and $y$. Then
$\mathrm{dist}(v_{i},[x_{1},\dots,x_{n}])$ is equal to the minimal distance
between $v_{i}$ and the line connecting $x$ and $y$. A brief calculation using
Lemma 6 shows that, for any $x,y\in A$, this distance is equal to

$\rho\,\frac{\sqrt{1+\cos(\alpha_{i})}}{\sqrt{2}},\quad\text{where}\quad\alpha_{i}=\angle(x,v_{i},y)\in(0,\pi),$
(19)

thus concluding the proof. ∎

## Acknowledgments

JP is supported by the German Research Foundation (DFG) under project
516672205 and by the Austrian Science Fund (FWF) under project P-32405.

Part of this work has been carried out during MS’s stay at the Department of
Mathematics of CWRU whose hospitality is gratefully acknowledged. MS’s stay
was supported by the State of Upper Austria. MS is supported by the Austrian
Science Fund (FWF) under project P-32405. This research was funded in whole or
in part by the Austrian Science Fund (FWF) [Grant DOI: 10.55776/P32405;
10.55776/J4777].

EMW is supported by NSF grant DMS-2103482.

Further, we thank the Hausdorff Research Institute for Mathematics, University
of Bonn, for providing an excellent working environment during the Dual
Trimester Program _Synergies between modern probability, geometric analysis
and stochastic geometry_.

## References

  * [1] I. Bárány.  Intrinsic volumes and $f$-vectors of random polytopes.  Math. Ann., 285(4):671–699, 1989.
  * [2] I. Bárány.  Random polytopes in smooth convex bodies.  Mathematika, 39(1):81–92, 1992.
  * [3] I. Bárány and C. Buchta.  Random polytopes in a convex polytope, independence of shape, and concentration of vertices.  Math. Ann., 297(3):467–497, 1993.
  * [4] H. Bräker, T. Hsing, and N. H. Bingham.  On the Hausdorff distance between a convex set and an interior random convex hull.  Adv. in Appl. Probab., 30(2):295–316, 1998.
  * [5] V.-E. Brunel.  Uniform behaviors of random polytopes under the Hausdorff metric.  Bernoulli, 25(3):1770–1793, 2019.
  * [6] L. Dümbgen and G. Walther.  Rates of convergence for random approximations of convex sets.  Adv. in Appl. Probab., 28(2):384–393, 1996.
  * [7] S. Glasauer and R. Schneider.  Asymptotic approximation of smooth convex bodies by polytopes.  Forum Math., 8(3):363–377, 1996.
  * [8] I. S. Gradshteyn and I. M. Ryzhik.  Table of integrals, series, and products.  Elsevier/Academic Press, Amsterdam, seventh edition, 2007.
  * [9] G. Last and M. Penrose.  Lectures on the Poisson process, volume 7 of Institute of Mathematical Statistics Textbooks.  Cambridge University Press, Cambridge, 2018.
  * [10] J. Prochno, C. Schütt, and E. M. Werner.  Best and random approximation of a convex body by a polytope.  J. Complexity, 71:Paper No. 101652, 19, 2022.
  * [11] M. Reitzner.  Random points on the boundary of smooth convex bodies.  Trans. Amer. Math. Soc., 354(6):2243–2278, 2002.
  * [12] M. Reitzner, C. Schütt, and E. M. Werner.  The convex hull of random points on the boundary of a simple polytope.  Discrete Comput. Geom., 69(2):453–504, 2023.
  * [13] A. Rényi and R. Sulanke.  Über die konvexe Hülle von $n$ zufällig gewählten Punkten.  Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 2:75–84 (1963), 1963.
  * [14] A. Rényi and R. Sulanke.  Über die konvexe Hülle von $n$ zufällig gewählten Punkten. II.  Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 3:138–147 (1964), 1964.
  * [15] R. Schneider.  Random approximation of convex sets*.  Journal of Microscopy, 151(3):211–227, 1988.
  * [16] C. Schütt.  Random polytopes and affine surface area.  Math. Nachr., 170:227–249, 1994.
  * [17] C. Schütt and E. M. Werner.  Polytopes with vertices chosen randomly from the boundary of a convex body.  In Geometric aspects of functional analysis, volume 1807 of Lecture Notes in Math., pages 241–422. Springer, Berlin, 2003.
  * [18] G. Walther.  On a generalization of Blaschke’s rolling theorem and the smoothing of surfaces.  Math. Methods Appl. Sci., 22(4):301–316, 1999.