On uniform performances of random polytopes and their functionals in convex bodies
Victor-Emmanuel Brunel
Cowles Foundation for Economics
Yale University
victor-emmanuel.brunel@yale.edu
In a previous paper we considered the random polytope defined as the convex hull of $n$ i.i.d. random points uniformly distributed in a convex body and we focused on the Nikodym distance between that convex body and the random polytope. We proved a uniform deviation inequality, yielding tight moment inequalities in a minimax sense. In this paper, we use a different technique in order to prove similar types of inequalities for the Hausdorff distance between the random polytope and the convex body. We no longer restrict ourselves to the case of uniform distributions. However, our results allow to recover and improve some known inequalities for the convex hull of uniform points in a convex body or on its boundary. We also prove moment inequalities for some class of functionals of the random polytope, including mean width as a special case.
Article2.tex
\documentclass[11pt]{article}

\usepackage{amssymb,amsbsy,amsmath,amscd,amsthm,amsfonts,MnSymbol}
\usepackage{cite}
\usepackage[utf8]{inputenc}
\usepackage{enumerate,hyperref}
\usepackage{dsfont}
\usepackage{graphicx}

%\usepackage[top=2.5cm,bottom=2.5cm,right=2.5cm,left=2.5cm]{geometry}


\hypersetup{
hidelinks
}


\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{condition}{Assumption}
\newtheorem{remarque}{Remark}
\newtheorem{exemple}{Exemple}
\newtheorem{lemma}{Lemma}
\newtheorem{remark}{Remark}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem*{AssumptionA}{Assumption A}


\newcommand{\R}{\mathbb R}
\newcommand{\PP}{\mathbb P}
\newcommand{\E}{\mathbb E}
\newcommand{\K}{\mathcal K_d}
\newcommand{\N}{\mathbb N}

\newcommand*\diff{\mathop{}\!\mathrm{d}}


\title{\textbf{On uniform performances of random polytopes and their functionals in convex bodies}}
\author{Victor-Emmanuel Brunel\\
   Cowles Foundation for Economics, Yale University\\
   \texttt{victor-emmanuel.brunel@yale.edu}}


\date{}




\begin{document}

\maketitle


\begin{abstract}
   In a previous paper we considered the random polytope defined as the convex hull of $n$ i.i.d. random points uniformly distributed in a convex body and we focused on the Nikodym distance between that convex body and the random polytope. We proved a uniform deviation inequality, yielding tight moment inequalities in a minimax sense. In this paper, we use a different technique in order to prove similar types of inequalities for the Hausdorff distance between the random polytope and the convex body. We no longer restrict ourselves to the case of uniform distributions. However, our results allow to recover and improve some known inequalities for the convex hull of uniform points in a convex body or on its boundary. We also prove moment inequalities for some class of functionals of the random polytope, including mean width as a special case.
\end{abstract}

\smallskip
\noindent \textbf{Keywords.} convex body, convex hull, deviation inequality, Hausdorff distance, random polytope



\section{Preliminaries and notation}

\subsection{Introduction}
Among all types of random polytopes defined in the litterature, we focus in this paper on convex hulls of finitely many independent and identically (i.i.d.) random points whose probability measure is supported on a convex body $K$ in the Euclidean space $\R^d$. From now on, we denote this convex hull by $\widehat K_n$, where $n$ is the number of random points. We often refer to these points as \textit{observations} and to $K$ as their \textit{support}. The dimension $d$ of the ambiant space is a fixed positive integer. We call \textit{convex body} in $\R^d$ any convex and compact subset of $\R^d$ with positive volume, i.e., of full dimension. We are interested in the performance of $\widehat K_n$ as an estimator of the body $K$. In \cite{Brunel13''}, we considered the case where uniformly distributed observations in $K$ and we studied the Nikodym distance between $\widehat K_n$ and $K$, i.e., the volume of the symmetric difference between $\widehat K_n$ and $K$. We proved the existence of two positive constants $\tau$ and $c$ which depend on the dimension $d$ only, for which the following holds. For all convex body $K\subset \R^d$, all $n\geq 1$ and all positive real number $x$, $$\frac{|\widehat K_n\triangle K|}{|K|}\leq \tau n^{-\frac{2}{d+1}} +\frac{x}{n},$$ with probability at least $\displaystyle{1-c e^{-\frac{x}{d^d}}}$.
Here, $|\cdot|$ stands for the volume and $\triangle$ is the symmetric difference. Note that the denominator $d^d$ in the exponential term becomes very large when the dimension $d$ grows and we believe it could be much improved by refining the technique of our proof. 

In the present work, we investigate the behaviour of the Hausdorff distance between $\widehat K_n$ and $K$, without necessarily restrincting to the case of uniform distribution. The Hausdorff distance between two sets $A_1$ and $A_2$ is defined as
$$d_H(A_1,A_2)=\inf\{\varepsilon>0/A_1\subseteq A_2+\varepsilon B_d(0,1) \mbox{ and } A_2\subseteq A_1+\varepsilon B_d(0,1)\},$$
where $B_d(a,r)$ is the closed $d$-dimensional Euclidean ball with center $a\in\R^d$ and radius $r\geq 1$.

The Hausdorff distance between the random polytope $\widehat K_n$ and the support $K$ has been studied under various assumptions in the litterature. Bàràny \cite{Barany1989} showed that if $X_1,\ldots,X_n$ are uniformly distributed in a $d$-dimensional convex body $K$ with twice continuously differentiable boundary and positive Gaussian curvature, then $\displaystyle{\E\left[d_H(\widehat K_n, K)\right]}$ is exactly of the order $\displaystyle{\left(\frac{\ln n}{n}\right)^{2/(d+1)}}$, with constant factors that depend on $K$. In the planar case ($d=2$), Korostelev and Tsybakov \cite{KorostelevTsybakov1994} proved a similar result, with constants that do not depend on $K$, under the extra assumption that a ball of given radius rolls freely on the inner side of $\partial K$. This assumption is frequent in the litterature, see for instance \cite{BoroczkyFodorReitznerVigh2009,Pateiro2008} and \cite{Walther1999} for more details about the free rolling ball property. Korostelev and Tsybakov \cite{KorostelevTsybakov1994} also proved that under the same assumptions, no random set achieves a strictly better uniform rate of convergence than that of $\widehat K_n$, i.e., $\displaystyle{\left(\frac{\ln n}{n}\right)^{2/3}}$, with respect to the expected Hausdorff distance of $\widehat K_n$ to the true support $K$.

Dümbgen and Walther \cite{DumbgenWalther1996} considered general distributions on convex bodies in order to show as particular cases that if the boundary of a convex body $K$ satisfies some smoothness condition, then almost surely,
$$d_H(\widehat K_n, K)=O\left(\left(\frac{\ln n}{n}\right)^\frac{2}{d+1}\right)$$
if the random points are uniformly distributed in $K$ and
$$d_H(\widehat K_n, K)=O\left(\left(\frac{\ln n}{n}\right)^\frac{2}{d-1}\right)$$
if they are uniformly distributed on the boundary of $K$. In the case of uniform distribution in a convex body $K$, they also showed that under no smoothness assumption on the boundary of $K$,
$$d_H(\widehat K_n, K)=O\left(\left(\frac{\ln n}{n}\right)^\frac{1}{d}\right) \hspace{4mm} \mbox{ almost surely},$$
with constant factors that depend on $K$ and $d$.

More precisely, when $X_1,\ldots,X_n$ are i.i.d. random points of $\partial K$ with a smooth density and if $\partial K$ is smooth enough, Glasauer and Schneider \cite{GlasauerSchneider1996} computed the limit in probability of $\displaystyle{\left(\frac{\ln n}{n}\right)^\frac{2}{d-1}d_H(\widehat K_n, K)}$. Schneider \cite{Schneider2004} conjectured that this limit holds almost surely.

We propose uniform deviation inequalities for the Hausdorff distance between the random polytope $\widehat K_n$ and an enclosing convex body $K$ of the support of the points $X_1,\ldots,X_n$ under general assumptions on the behavior of that distribution near the boundary of $K$. In most cases, $K$ will be equal to the support itself, or to its convex hull. By uniform, we mean that the bounds depend neither on $K$ nor on the distribution itself. Particular cases include uniform probability measures in smooth convex bodies, in polytopes and on the boundary of smooth convex bodies. We also extend the optimality result proved in \cite{KorostelevTsybakov1994} in the case of uniform distributions to higher dimensions.

This paper is organised as follows. After displaying our notation and preliminary definitions, we prove our main theorems in Section \ref{SectionMain}. The first one bounds the performance of the random polytope, under assumptions made in the same spirit as in \cite{DumbgenWalther1996} and the second one concerns its functionals, including its mean and maximal widths. That section ends with a discussion on misspecification, i.e., about the non convex case. In Section \ref{UnifCase0}, we derive from our main theorems upper bounds on the performance of the random polytope in three cases: uniform distribution in smooth convex bodies, in polytopes and on the boundary of smooth convex bodies. For the case of polytopes, we give non uniform results, in order to avoid making too complex assumptions on the facial structure. For that of uniform distribution in smooth convex bodies, we extend the optimality result of \cite{KorostelevTsybakov1994}. Section \ref{SectionProof} is devoted to the proofs.



\subsection{Notation and introductory considerations}

Recall that throughout all this work, the dimension $d$ is a fixed positive number. We denote by $\mathcal K_d$ the class of all convex bodies in $\R^d$ and by $\mathcal K_d^{(1)}$ the class of all convex bodies included in the closed unit Euclidean ball in $\R^d$.

If $p$ is a positive integer, the $p$-dimensional closed Euclidean ball with center $a\in\R^p$ and radius $r>0$ is denoted by $B_p(a,r)$ and the $p-1$-dimensional Euclidan unit sphere is denoted by $S^{p-1}$ (so, $S^{p-1}\subseteq \R^p$). Th $p$-dimensional volume of $B_p(0,1)$ is denoted by $\beta_p$. 

We denote by $\|\cdot\|$, without any subscript, the Euclidean norm in $\R^d$.

The interior of a set $A$ is denoted by $int(A)$. Its boundary is denoted by $\partial A$.

The support function $h_A$ of a compact set $A\subset \R^d$ is the mapping
\begin{align*}
	h_A : \R^d & \rightarrow \R \\
	u & \mapsto \max\{\langle u,x\rangle/x\in A\},
\end{align*}
where $\langle\cdot,\cdot\rangle$ stands for the canonical inner product in $\R^d$. Note that if $A$ is a compact set, then $h_A=h_{conv(A)}$, where $conv(A)$ is the convex hull of $A$.

We recall the two following properties of support functions. If $K$ is a convex body, then $h_K$ is positively homogenous, i.e.,
\begin{equation} \label{prop1}
	\forall u\in\R^d, \forall \lambda\geq 0, h_K(\lambda u)=\lambda h_K(u)
\end{equation}
and it satisfies the triangle inequality:
\begin{equation} \label{prop2}
	\forall u,v\in\R^d, h_K(u+v) \leq h_K(u)+h_K(v).
\end{equation}
In particular, \eqref{prop2} implies the reverse triangle inequality
\begin{equation} \label{prop3}
	\forall u,v\in\R^d, h_K(u-v) \geq h_K(u)-h_K(v).
\end{equation}

We define the pseudo-norm $\|\cdot\|_K$ associated to a convex body $K$ (also called the Minkowski functional of $K$) as
$$\|x\|_K=\min\{\lambda\geq 0 / x\in\lambda K\}, \forall x\in\R^d.$$
This is a norm if and only if $K$ is symmetric, i.e., $K=-K$. If $K=S^{d-1}$, then $\|\cdot\|_K$ is the Euclidean norm in $\R^d$. 

The polar body $K^\circ$ of a convex body $K$ is the convex set defined as
$$K^\circ=\{x\in\R^d/\forall y\in K, <x,y>\leq 1\}.$$
If $0\in int(K)$, then $K^\circ$ is compact, hence a convex body and 
\begin{equation} \label{propPolar}
\forall x\in\R^d, h_K(x)=\|x\|_{K^\circ}.
\end{equation}
It is also true that for bounded $K$, $0$ is an interior point of $K^\circ$.

Let us state a property of the Hausdorff distance, which will be of interest for our purposes. The Hausdorff distance between two convex bodies $K$ and $K'$ can be expressed in terms of their support functions:
$$d_H(K,K')=\sup_{u\in S^{d-1}} |h_K(u)-h_{K'}(u)|.$$ 

If $K\in\mathcal K_d$, $u\in S^{d-1}$ and $\varepsilon\geq 0$, we denote by $C_K(u,\varepsilon)$ the cap of $K$ in the direction of $u$ and of width $\varepsilon$:
$$C_K(u,\varepsilon)=\left\{x\in K \hspace{2mm} / \hspace{2mm} \langle u,x \rangle \geq h_K(u) \right\}.$$
When there is no ambiguity, we may omit the subscript $K$, especially in the proofs. 

We denote by $\Delta(\R^d)$ the collection of all probability measures on $\R^d$ equipped with its Borel $\sigma$-algebra. For $\mu\in\Delta(\R^d)$, we denote by $\E_\mu$ the corresponding expectation operator. The support of a probability measure $\mu$ in $\R^d$ is defined as follows. Let $\mathcal O_\mu$ be the collection of all open subsets $O\subseteq \R^d$ with $\mu(O)=0$ and define $\displaystyle{\Omega_\mu=\bigcup_{O\in\mathcal O_\mu} O}$ (set $\Omega_\mu=\emptyset$ if $\mathcal O_\mu$ is empty). Because $\R^d$ is a metric space, this is the largest open subset of $\R^d$ mapped to zero by $\mu$, inclusionwise. The support of $\mu$, which we denote by $Supp(\mu)$, is the closed set defined as the complement of $\Omega_\mu$.
 
If $\alpha$, $L$ and $\varepsilon_0$ are positive numbers with $\varepsilon_0\leq 1$, let 
\begin{align*}
	\mathcal M(\alpha,L,\varepsilon_0)=\big\{(\mu,K)\in & \Delta(\R^d)\times\mathcal K_d^{(1)} \hspace{2mm} / \hspace{2mm} Supp(\mu)\subseteq K, \\
	& \forall u\in S^{d-1},\forall \varepsilon\in [0,\varepsilon_0], \mu\left(C_K(u,\varepsilon)\right) \geq L\varepsilon^\alpha\big\}.
\end{align*}
Note that if $(\mu,K)\in\mathcal M(\alpha,L,\varepsilon_0)$ for some positive numbers $\alpha,L,\varepsilon_0$, then $K$ is necessarily the convex hull of $supp(\mu)$. Indeed, $K$ is convex and it is easy to see that every closed halfspace that contains either $supp(\mu)$ of $K$ necessarily contains the other as well. For the sake of simplicity, we may also refer to $K$ as the support of $\mu$.

Roughly speaking, if $\mu$ is the uniform measure in a convex body $K$ with smooth boundary, then the couple $(\mu,K)$ belongs to the class $\mathcal M(\alpha,L,\varepsilon_0)$ for $\displaystyle{\alpha=\frac{d+1}{2}}$ and $L, \varepsilon_0$ suitably chosen. If $\mu$ is uniform in a polytope $K$, then one can take $\displaystyle{\alpha=d}$ and if $\mu$ is the uniform distribution on the boundary of a smooth convex body, $\displaystyle{\alpha=\frac{d-1}{2}}$. More details on this account will be given in the sequel.

If $n$ is a positive integer and $X_1,\ldots,X_n$ are i.i.d. random points uniformly distributed in some convex body $K$, we denote by $\PP_K$ their joint law (for the sake of notation, we again prefer not to show its dependency on $n$) and by $\E_K$ the corresponding expectation operator. Similarly, if the $n$ i.i.d. random points are uniformly distributed on the boundary of a convex body $K$, we denote by $\PP_{\partial K}$ their joint law and by $\E_{\partial K}$ the corresponding expectation operator.

If $(u_n)$ and $(v_n)$ are two positive sequences, we write that $u_n=O(v_n)$ or, equivalently, $v_n=\omega(u_n)$, if the sequence $(u_n/v_n)$ is bounded and $u_n\asymp v_n$ if $u_n=O(v_n)$ and $u_n=\omega(v_n)$ simulatenously.

Throughout the rest of the paper, we denote by $\displaystyle{C_\alpha=\inf_{t>0}\frac{(1+t)^\alpha}{1+t^\alpha}>0}$ for any positive number $\alpha$.  


\section{Estimation of the support of a measure} \label{SectionMain}

\subsection{Performance of the random polytope}

In this section, we quantify the performance of the random polytope $\widehat K_n$ in terms of deviation and moment inequalities for $d_H(\widehat K_n, K)$. In other words, we ask how small this distance can be with high probability, or in expectation. We assume that the probability measure $\mu$ of the i.i.d. observed points and the convex body $K$ satisfy $(\mu,K)\in\mathcal M(\alpha,L,\varepsilon_0)$, for some positive numbers $\alpha, L$ and $\varepsilon_0$. From a statistical point of view, the random polytope $\widehat K_n$ can be interpreted as an estimator of $K$, if $K$ is unknown. In that case, one wish to recover $K$ from the observed points $X_1,\ldots,X_n$ only. One advantage of the estimator $\widehat K_n$ is that it is adaptive to $\mu$, i.e., its computation does not require any knowledge about $\mu$. In Section \ref{sectionUniform}, we will show that under some precise condition, $\widehat K_n$ is an optimal estimator of $K$ in a minimax sense.



\begin{theorem}\label{theorem21}
Let $d$ and $n$ be positive integers and $\alpha,L,\varepsilon_0$ be positive numbers with $0<\varepsilon_0\leq 1$. Set $\displaystyle{\tau_1=\max\left(1,\frac{d}{C_\alpha\alpha L}\right)}$, $\displaystyle{a_n=\left(\frac{\tau_1\ln n}{n}\right)^\frac{1}{\alpha}}$ and $\displaystyle{b_n=n^{-\frac{1}{\alpha}}}$. The random polytope $\widehat K_n$ satisfies the following uniform deviation inequality on the class $\mathcal M(\alpha,L,\varepsilon_0)$: For all nonnegative number $x$ satisfying $\displaystyle{a_n+b_n x\leq \varepsilon_0}$
	$$\sup_{(\mu,K)\in\mathcal M(\alpha,L,\varepsilon_0)} \mu\left[d_H(\widehat {K_n},K)\geq 2a_n + 2b_n x\right] \leq 12^d\exp\left(-C_\alpha L x^\alpha\right).$$
\end{theorem}



\begin{remark}
	\begin{itemize}
		\item If $\displaystyle{a_n+b_n x> 1}$, the upper bound in Theorem \ref{theorem21} can be replaced with $0$, since for all $(\mu,K)\in \mathcal M(\alpha,L,\varepsilon_0)$, $$d_H(\widehat K_n,K)\leq 2 \hspace{4mm} \mu\mbox{-almost surely}.$$
		\item For $\displaystyle{\varepsilon_0\leq a_n+b_n x\leq 1}$, the upper bound in Theorem \ref{theorem21} can be replaced with its value at $\displaystyle{x=(\varepsilon_0-a_n)b_n^{-1}}$, since the left side of the inequality is a nonincreasing function of $x$.
		\item It is important to notice that the constant factors in Theorem \ref{theorem21} are much smaller than in Theorem 1 in \cite{Brunel13''} when the dimension $d$ becomes large. Unlike for those constants in \cite{Brunel13''}, we believe that the factor $12^d$ cannot be much improved in general. 
	\end{itemize}
\end{remark}


Theorem \ref{theorem21} yields the following moment inequalities.

\begin{corollary}\label{corollary2}
	Let $d$ be a positive integer and $\alpha,L,\varepsilon_0$ be positive numbers with $0<\varepsilon_0<1$. Then, for all real number $q\geq 1$,
	$$\sup_{(\mu,K)\in\mathcal M(\alpha,L,\varepsilon_0)} \E_\mu\left[d_H(\widehat K_n,K)^q\right]=O\left(\left(\frac{\ln n}{n}\right)^\frac{q}{\alpha}\right).$$
\end{corollary}




\subsection{Estimation of functionals of $K$}

Previously, we focused on the performance of $\widehat K_n$, as an estimator of $K$. The set $K$ itself may not be of main interest to the statistician. In this section, we study a class of functionals of $K$ and we bound the performances of the corresponding functionals of $\widehat K_n$ as \textit{plug-in} estimators of those of $K$. In this context, a functional is a mapping $T:\mathcal K_d\longrightarrow \R$. If $K$ is unknown, a functional $T(K)$ can be estimated using the so called \textit{plug-in} estimator $T(\widehat K_n)$. Plug-in estimators are often suboptimal. For instance, if $T$ is the volume, i.e., $T(K)=|K|$ and $\mu$ is the uniform probability measure in $K$, \cite{Gayraud1997} proved that the plug-in estimator $|\widehat K_n|$ is suboptimal and proposed another estimator, based on a three-fold sample splitting, that achieves optimality in a minimax sense. Let us introduce some new notation.

The unit sphere $S^{d-1}$ is equipped with the Borel $\sigma$-algebra that it inherits from $\R^d$. For any real number $p\geq 1$ and any measurable function $f:S^{d-1}\rightarrow \R$, denote by 
$$\|f\|_p=\left(\int_{S^{d-1}} |f(u)|^p d\sigma(u)\right)^\frac{1}{p},$$
where $\sigma$ is the surface area measure on the sphere with the normalisation $\displaystyle{\sigma\left(S^{d-1}\right)=1}$ and
$$\|f\|_\infty=\sup_{u\in S^{d-1}} |f(u)|,$$
provided these quantities are finite. 

If $K\in\mathcal K_d$, we still denote by $h_K$ the restriction of its support function to the unit sphere and we define
\begin{align*}
	\phi_K : S^{d-1} & \rightarrow \R \\
	u & \mapsto h_K(u)+h_K(-u).
\end{align*}
We are interested in functionals of the form $T_p(K)=\|h_K\|_p$ or $S_p(K)=\|\phi_K\|_p$, for real numbers $p\geq 1$ or $p=\infty$. Extensions to broader classes of functionals is possible. Note that $S_1$ is the mean width and $S_\infty$ is the maximum width. Asymptotics of the mean width of $\widehat K_n$ are known in many cases. When $\mu$ is uniform in a smooth convex body $K$, it is well known that 
$$S_1(K)-\E_K\left[S_1(\widehat K_n)\right] \underset{n\to\infty}{\longrightarrow} c_Kn^{-\frac{2}{d+1}},$$
where $c_K$ is a positive number that depends on $K$, see \cite{SchneiderWieacker1980, BoroczkyFodorReitznerVigh2009} for explicit formulas. If $\mu$ is uniform in a polytope $K$, Schneider \cite{Schneider1987} proved that 
$$S_1(K)-\E_K\left[S_1(\widehat K_n)\right] \underset{n\to\infty}{\longrightarrow} c'_Kn^{-\frac{1}{d}},$$
for another porisitve constant $c'_K$ that also depends on $K$.
When $\mu$ is supported on the boundary of a smooth convex body $K$ with a positive density $g$ with respect to the surface area measure of $\partial K$, Müller \cite{Muller1989} showed that
$$S_1(K)-\E_K\left[S_1(\widehat K_n)\right] \underset{n\to\infty}{\longrightarrow} c''_{g,K}n^{-\frac{2}{d-1}},$$
where the positive number $c''_{g,K}$ depends on $g$ and $K$.
Here, we prove moment inequalities for $S_1(\widehat K_n)$ as well as for the other functionals $S_p, T_p, p\in[1,\infty)\cup\{\infty\}$. In \cite{BoroczkyFodorReitznerVigh2009} it is shown that for the uniform distribution in a smooth convex body $K$, the variance of $S_1(\widehat K_n)$ is of the order $\displaystyle{n^{-\frac{d+3}{d+1}}}$, up to constant factors that depend on $K$. Our results do not allow to recover such estimates of the variance because we do not bound moments of the centered versions of the functionals.

Let $p\in [1,\infty)\cup\{\infty\}$ and $q\geq 1$ be a real number. If $K$ and $K'$ are two convex bodies, then by the triangle inequality,
\begin{equation} \label{TriangleIneqT}
	\left|T_p(K)-T_p(K')\right|^q \leq \|h_K-h_{K'}\|_p^q
\end{equation}
and
\begin{equation} \label{TriangleIneqS}
	\left|S_p(K)-S_p(K')\right|^q \leq \|\phi_K-\phi_{K'}\|_p^q.
\end{equation}
In the next Theorem, we give uniform upper bounds for $\displaystyle{\E_\mu\left[\|h_K-h_{\widehat K_n}\|_p^q\right]}$ and $\displaystyle{\E_\mu\left[\|\phi_K-\phi_{\widehat K_n}\|_p^q\right]}$ when $(\mu,K)$ ranges in $\mathcal M(\alpha,L,\varepsilon_0)$ for given positive numbers $\alpha,L,\varepsilon_0$. Note that the case $p=\infty$ is treated in Corollary \ref{corollary2} and we treat here only finite values of $p$.
\begin{theorem}\label{theorem2'}
	Let $d$ be a positive integer, $\alpha,L>0$, $0<\varepsilon_0\leq 1$ and $p,q\geq 1$ be real numbers. Then,
	$$\sup_{(\mu,K)\in\mathcal M(\alpha,L,\varepsilon_0)} \E_\mu\left[\|h_K-h_{\widehat K_n}\|_p^q\right]=O\left(n^{-\frac{q}{\alpha}}\right)$$
	and 
	$$\sup_{(\mu,K)\in\mathcal M(\alpha,L,\varepsilon_0)} \E_\mu\left[\|\phi_K-\phi_{\widehat K_n}\|_p^q\right]=O\left(n^{-\frac{q}{\alpha}}\right).$$
\end{theorem}
As opposite to the case $p=\infty$ (see Corollary \ref{corollary2}), the logarithmic factor can actually be dropped for finite values of $p$. We explain this phenomenon by the fact that $L^\infty$ norms are more restrictive than $L^p$ norms ($p\in[1,\infty)$), since they capture the largest values of a function, no matter the size of the subset where large values are achieved. When $\mu$ is the uniform probability measure in a smooth convex body, Theorem \ref{theorem3} in Section \ref{sectionUniform} shows that the logarithmic factor cannot be avoided for $p=\infty$. 

By \eqref{TriangleIneqT} and \eqref{TriangleIneqS}, next Corollary is a direct consequence of Theorem \ref{theorem2'}.

\begin{corollary}
	Let $d$ be a positive integer, $\alpha,L>0$, $0<\varepsilon_0\leq 1$ and $p,q\geq 1$ be real numbers. Then,
	$$\sup_{(\mu,K)\in\mathcal M(\alpha,L,\varepsilon_0)} \E_\mu\left[|T_p(K)-T_p(\widehat K_n)|^q\right]=O\left(n^{-\frac{q}{\alpha}}\right)$$
	and
	$$\sup_{(\mu,K)\in\mathcal M(\alpha,L,\varepsilon_0)} \E_\mu\left[|S_p(K)-S_p(\widehat K_n)|^q\right]=O\left(n^{-\frac{q}{\alpha}}\right).$$
\end{corollary}



\subsection{Misspecification: The non convex case}

In the setup of random polytopes, convexity of $K$ is a natural assumption. However, in practice, this assumption is very strong. In particular, it could be misleading and the model \textit{misspecified}: For instance, the probability measure of the observed points $X_1,\ldots,X_n$ may be supported in a non convex set or on the boundary of a non convex set. In that case, the random convex hull $\widehat K_n$ does not estimate the support $K$ itself, but instead, its convex hull. Define the new classes $\mathcal M'(\alpha,L,\varepsilon_0)$ as
\begin{align*}
	\mathcal M'(\alpha,L,\varepsilon_0)=\big\{(\mu,K)\in & \Delta(\R^d)\times\mathcal C_d^{(1)} \hspace{2mm} / \hspace{2mm} Supp(\mu)\subseteq K, \\
	& \forall u\in S^{d-1},\forall \varepsilon\in [0,\varepsilon_0], \mu\left(C_K(u,\varepsilon)\right) \geq L\varepsilon^\alpha\big\},
\end{align*}
where $\mathcal C_d^{(1)}$ is the class of all compact subsets of $\R^d$ with positive volume. Then, all results stated in the previous sections (theorems \ref{theorem21}, \ref{theorem2'} and their subsequent corollaries) remain valid if $\mathcal M(\alpha,L,\varepsilon_0)$ is replaced with the new class $\mathcal M'(\alpha,L,\varepsilon_0)$ and $d_H(\widehat K_n,K)$ is replaced with $d_H(\widehat K_n,conv(K))$. The key argument for this statement is the simple fact that the support function of a compact set is equal to that of its convex hull. This is of particular interest if one wishes to estimate functionals of a compact, but not necessarily convex set, such as its mean width. For instance, adaptation of Theorem \ref{theorem2'} to the non convex case shows that the mean width of a compact, non convex set can be recovered at the speed $\displaystyle{n^{-\frac{1}{\alpha}}}$ under some assumptions on $\mu$. A case of particular interest is when $\mu$ is the uniform probability measure in a compact set $K$ which has a freely rolling ball of a given radius $r$ along the the inside part of its boundary (see Figure \ref{etiquette2}). In that case, similarly to what we will see in Section \ref{unifCase}, the convex hull of $K$ can be recovered by $\widehat K_n$ at the speed $\displaystyle{\left(\frac{\ln n}{n}\right)^\frac{2}{d+1}}$ and its functionals $S_p(K)$ and $T_p(K)$, for $p\in[1,\infty)$, are estimated by the plug-in estimators at the speed $n^{-\frac{2}{d+1}}$.


\begin{figure}
\centering
   \includegraphics[scale=0.15]{Figure2}
   \caption{\label{etiquette2} The non convex case: $K$ is a compact set with a free rolling ball on the inner side of its boundary, of give radius $r$.}
\end{figure}


\section{The case of uniform probability measures}\label{UnifCase0}

\subsection{In a smooth convex body}

\subsubsection{Performance of the random convex hull} \label{unifCase}

Let $r$ be a positive number. We say that a compact set $K\subset \R^d$ satisfies the $r$-rolling condition if at each point $x$ of its boundary $\partial K$, there exists a Euclidean ball $B$ with radius $r$, included in $K$ and containing the point $x$ (see Figure \ref{etiquette2}). For all real numbers $r\in (0,1]$, we denote by $\mathcal K_{d,r}^{(1)}$ the class of all convex bodies that satisfy the $r$-rolling condition and that are included in the centered unit Euclidean ball. If $K\in\mathcal K_{d,r}^{(1)}$ and $\mu$ is the uniform probability measure in $K$, it is easy to see that $(\mu,K)\in\mathcal M(\alpha,L,\varepsilon_0)$ for $\displaystyle{\alpha=\frac{d+1}{2}, L=\frac{2\beta_{d-1}r^\frac{d-1}{2}}{\beta_d(d+1)}}$ and $\varepsilon_0=r$.
Indeed, if $B$ is any Euclidean ball with radius $r$, then for all $u\in S^{d-1}$ and $0\leq\varepsilon\leq r$,
\begin{align} \label{radiuscap}
	\mu\left(C_K(u,\varepsilon)\right) & = \frac{|C_K(u,\varepsilon)|}{|K|} \nonumber \\
	& \geq \frac{|C_B(u,\varepsilon)|}{\beta_d} \nonumber \\
	& = \frac{1}{\beta_d}\int_0^\varepsilon \left(x(2r-x)\right)^\frac{d-1}{2}\beta_{d-1} dx \nonumber \\
	& \geq \frac{\beta_{d-1}r^\frac{d-1}{2}}{\beta_d}\int_0^\varepsilon x^\frac{d-1}{2} dx \nonumber \\
	& = \frac{2\beta_{d-1}r^\frac{d-1}{2}}{\beta_d(d+1)}\varepsilon^\frac{d+1}{2}.
\end{align}


%\begin{figure}[!h]
%\centering
%   \includegraphics[scale=0.4]{path6649}
%   \caption{\label{etiquette} The rolling condition: $K\in\mathcal K_{r,d}^{(1)}$.}
%\end{figure}


Therefore, the following result is a direct consequence of Theorem \ref{theorem21}.
\begin{theorem}
	Let $d, n$ be positive integers and $0<r\leq 1$. Let $\displaystyle{L=\frac{2\beta_{d-1}r^\frac{d-1}{2}}{\beta_d(d+1)}}$, $\displaystyle{\tau=\max\left(1,\frac{d\beta_d}{C_\frac{d+1}{2}\beta_{d-1}r^\frac{d-1}{2}}\right)}$, $\displaystyle{a_n=\left(\frac{\tau\ln n}{n}\right)^\frac{2}{d+1}}$ and $\displaystyle{b_n=n^{-\frac{2}{d+1}}}$. The random polytope $\widehat K_n$ satisfies the following uniform deviation inequality on the class $\mathcal K_{d,r}^{(1)}$: For all nonnegative number $x$ satisfying $\displaystyle{a_n+b_n x\leq r}$
	$$\sup_{K\in\mathcal K_{d,r}^{(1)}} \PP_K\left[d_H(\widehat {K_n},K)\geq 2a_n + 2b_n x\right] \leq 12^d\exp\left(-C_\frac{d+1}{2} L x^\alpha\right).$$
\end{theorem}

As a consequence of this Theorem, we have the following uniform moment inequalities.

\begin{corollary}\label{corollary3}
	Let $d$ be a positive integer $0<r\leq 1$. Then, for all real number $q\geq 1$,
	$$\sup_{K\in\mathcal K_{d,r}^{(1)}} \E_K\left[d_H(\widehat K_n,K)^q\right]=O\left(\left(\frac{\ln n}{n}\right)^\frac{2q}{d+1}\right).$$
\end{corollary}
In the next section, we prove that these moment inequalities are tight in a minimax sense. 

As far as functionals are concerned, Theorem \ref{theorem2'} can also be applied in the present case, yielding

\begin{theorem}\label{theorem3'}
	Let $d$ be a positive integer and $0<r\leq 1$. Then, for all real number $q\geq 1$,
	$$\sup_{K\in\mathcal K_{d,r}^{(1)}}  \E_K\left[\|h_K-h_{\widehat K_n}\|_p^q\right]=O\left(n^{-\frac{2q}{d+1}}\right)$$
	and 
	$$\sup_{K\in\mathcal K_{d,r}^{(1)}}  \E_K\left[\|\phi_K-\phi_{\widehat K_n}\|_p^q\right]=O\left(n^{-\frac{2q}{d+1}}\right).$$
\end{theorem}
This theorem shows that the plug-in estimators of the functionals $T_p(K)$ and $S_p(K)$, for real numbers $p\geq 1$, perform in expectation at a speed at least $n^{-2/(d+1)}$, when $K$ is a convex body with a free rolling ball of give radius. As we discussed in the beginning of the section, this result was already known for the mean width $S_1(K)$.


\subsubsection{Optimality of the random convex hull in smooth convex bodies} \label{sectionUniform}

In \cite{Brunel2013''}, we showed that the random polytope $\widehat K_n$ is rate-optimal in a minimax sense, with respect to the Nikodym distance. Let us recall briefly this result. If $n$ is a positive integer and $X_1,\ldots,X_n$ are random variables mapping the probability space $(\Omega,\mathcal F,\PP)$ onto a given measurable space $\mathcal X$, we call a set valued statistic any set of the form $\widetilde K_n(X_1,\ldots,X_n)$, where $\widetilde K_n$ maps $\mathcal X^n$ to the set of all compact subsets of $\R^d$, such that the function
\begin{align*}
	\Omega\times \R^d & \rightarrow \{0,1\} \\
	(\omega,x) & \mapsto \left\{
	\begin{array}{ll}
		1  & \mbox{if } x\in \widetilde K_n\left(X_1(\omega),\ldots,X_n(\omega)\right) \\
		0 & \mbox{otherwise }
	\end{array}
\right.
\end{align*}
is measurable with respect to the product of $\mathcal F$ and the Borel $\sigma$-algebra of $\R^d$. For the sake of notation, we write $\widetilde K_n$ instead of $\widetilde K_n(X_1,\ldots,X_n)$. For instance, if $\mathcal X=\R^d$ and $X_1,\ldots,X_n$ are i.i.d. random points, then $\widehat K_n$ is a set valued statistic. If a set valued statistic $\widetilde K_n$ is aimed to approximate $K$, which may be unknown in practice, it is called an estimator of $K$ and the variables $|\widetilde K_n\triangle K|$ and $d_H(\widetilde K_n,K)$ are (measurable) random variables. A more general definition of set valued random variables can be found in \cite{Molchanov2005}, but it is not needed for our purposes. In \cite{Brunel2013''}, it is shown that for any estimator $\widetilde K_n$ of $K$, $\displaystyle{\sup_{K\in\mathcal K_d}\E_K\left[\frac{|\widetilde K_n\triangle K|}{|K|}\right]}$ never converges to zero faster than when $\widetilde K_n=\widehat K_n$, when $n\to\infty$. The random polytope $\widehat K_n$ is called rate-minimax optimal on the class $\mathcal K_d$, for the rescaled Nikodym distance. Next theorem, together with Corollary \ref{corollary2}, establishes rate minimax optimality of $\widehat K_n$ on the class $\mathcal K_{r,d}^{(1)}$, for the Hausdorff distance $d_H$.

\begin{theorem}\label{theorem3}
Let $d$ be a positive integer and $0<r<1$. Then, for all real number $q\geq 1$ and any set estimator $\widetilde K_n$,
$$\sup_{K\in\mathcal K_{r,d}^{(1)}} \E_K\left[d_H(\widetilde K_n,K)^q\right] = \omega\left(\left(\frac{\ln n}{n}\right)^\frac{2q}{d+1}\right).$$
\end{theorem}

We restrict $r$ to be strictly less than 1 in Theorem \ref{theorem3}, since when $r=1$, the class $\mathcal K_{1,d}^{(1)}$ is made of only one element, $B_d(0,1)$ and the trivial estimator $\widetilde K_n=B_d(0,1)$ satisfies $\displaystyle{\sup_{K\in\mathcal K_{1,d}^{(1)}} \E_K\left[d_H(\widetilde K_n,K)\right]=0}$.

In \cite{Brunel2013''} and \cite{Brunel13''}, the risk of $\widehat K_n$ was measured using the Nikodym distance rescaled by the volume of $K$, namely, $\displaystyle{\frac{|\widehat K_n\triangle K|}{|K|}}$. Rescaling with the volume of $K$ allowed to consider convex bodies $K$ not necessarily included in some given bounded set such as $B_d(0,1)$. Same is possible in our present case if the definition of the Hausdorff distance is slightly modified. This is the purpose of next section.

\subsubsection{Rescaled performance of the random convex hull}

For the uniform case, we propose another way of measuring the distance between the support $K$ and $\widehat K_n$, which allows to remove the restriction $K\subseteq B_d(0,1)$. Namely, we define the distance $d_L$ between two subsets $K$ and $K'$ of $\R^d$ as
\begin{align*}
	d_L&(K,K') = \\
	& \inf\{\varepsilon\geq 0 / \exists a\in R^d, a+(1-\varepsilon)(K-a)\subseteq K'\subseteq a+(1+\varepsilon)(K-a)\}.
\end{align*}
Note that $d_L$ does not properly define a distance since it is not symmetric. However, if $d_L(K,K')$ is sufficiently small, then $d_L(K,K')$ and $d_L(K',K)$ are roughly the same. One advantage of $d_L$ over $d_H$ is that it is invariant under any invertible affine transormation $T$: $d_L(K,K')=d_L(T(K),T(K'))$. In turn, considering $d_L$ instead of $d_H$ allows to get rid of the assumption $K\subseteq B_d(0,1)$ in our results.

For $0<r\leq 1$, let us denote by $\mathcal K_{r,d}$ the class of all convex bodies in $\R^d$ satisfying the $\widetilde r$-rolling condition, with $\displaystyle{\widetilde r=r\left(\frac{|K|}{\beta_d}\right)^{1/d}}$. 
By introducing the number $\widetilde r$ in this definition, we ensure that all convex bodies that are similar to $K$, i.e., obtained by rescaling, translating, rotating or reflecting $K$, will be in $\mathcal K_{d,r}$ as soon as $K$ is.


\begin{theorem}\label{theorem1}
	Let $d$ and $n$ be positive integers and $r\in (0,1]$. Set the positive constant $\displaystyle{\tau_3=\max\left(1,\frac{\beta_d}{\beta_{d-1}C_\frac{d+1}{2}r^d L}\right)}$, $\displaystyle{a_n=\left(\frac{\tau_3\ln n}{n}\right)^\frac{2}{d+1}}$ and $\displaystyle{b_n=n^{-\frac{2}{d+1}}}$. Then, the random polytope $\widehat K_n$ satisfies
	$$\sup_{K\in\mathcal K_{r,d}} \PP_K\left[d_L(\widehat K_n,K)\geq 2a_n + 2b_n x\right] \leq  6^d\exp\left(-\tau_3 x^\frac{d+1}{2}\right),$$
for all nonnegative real number $x$ with $a_n+b_n x\leq 1$.
\end{theorem}

\begin{remark}
	For $K\in\mathcal K_{r,d}$, since $\widehat K_n\subseteq K$ $\PP_K$-almost surely, $d_L(\widehat K_n,K)\leq 1$. Hence, the right side of the inequality in Theorem \ref{theorem1} can be replaced with $0$ if $a_n+b_n x$ exceeds $1$.
\end{remark}

Theorem \ref{theorem1}, together with the previous remark, implies the following moment inequalities.

\begin{corollary}\label{corollary1}
	Let $d$ be a positive integer and $r\in (0,1]$. Then, for all real number $q\geq 1$,
	$$\sup_{K\in\mathcal K_{r,d}} \E_K\left[d_L(\widehat K_n,K)^q\right]=O\left(\left(\frac{\ln n}{n}\right)^\frac{2q}{d+1}\right).$$
\end{corollary}



\subsection{In a polytope}

The polytopal case is more intricate and we choose only to present the heuristics here. Let $K$ be a polytope and $u\in S^{d-1}$. Let $H$ be the (unique) supporting hyperplane of $K$ in the direction $u$. Then, $K\cap H$ is a face of $K$ and let $k$ be its dimension, i.e., the dimension of its affine hull. As $\varepsilon\rightarrow 0$, $\PP_K\left[C_K(u,\varepsilon)\right]$ goes to zero as a polynomial of degree $d-k$ in $\varepsilon$. This speed of convergence is the fastest when $k=0$, i.e., when $H$ supports $K$ at a vertex. By a compacity argument, it follows that for all polytope $K$, $(\PP_K,K)\in\mathcal M(\alpha,L,\varepsilon_0)$ with $\alpha=d$ and $L$ and $\varepsilon_0$ being two positive numbers depending on $K$. Hence, 
$$\E_K\left[d_H(\widehat K_n, K)\right]=O\left(\left(\frac{\ln n}{n}\right)^{1/d}\right),$$
with constant factors that depend on $K$ through the parameters $L$ and $\varepsilon_0$. It is possible to write uniform deviation and moment inequalities by restricting the class of polytopes in such a way that $L$ and $\varepsilon_0$ do not depend on $K$ anymore, but the corresponding assumptions (similar to the free-rolling ball condition in the cas of smooth convex bodies) would be quite technical.

One comment seems necessary. In the case of uniform observations, Groemer \cite{Groemer1974} showed that when $K$ ranges in $\mathcal K_d$, $\displaystyle{\E_K\left[\frac{|\widehat K_n\triangle K|}{|K|}\right]}$ is maximal when $K$ is an ellipsoid (any ellipsoid, by affine invariance) and it was conjectured by Bàràny and Buchta \cite{BaranyBuchta1993} that it is minimal when $K$ is a simplex. What is known (see \cite{BaranyLarman1988}) is that it converges to zero at the fastest rate (in terms of $n$) when $K$ is a polytope. However, our results suggest that the opposite is true for $\E_K[d_H(\widehat K_n,K)]$: we showed that it converges at a speed at least $\displaystyle{\left(\frac{\ln n}{n}\right)^{2/(d+1)}}$ when $K$ is a Euclidean ball and at at least $\displaystyle{\left(\frac{\ln n}{n}\right)^{1/d}}$ when $K$ is a polytope. Hence, for the Hausdorff distance, the situation seems to be reversed as compared with the Nikodym distance.


\subsection{On the boundary of a smooth convex body}

In this section, we assume that $d\geq 2$ and we consider convex bodies in $\R^d$ that satisfy a rolling condition. Let us fix a positive number $r\in(0,1]$ and let $K\in\mathcal K_{r,d}^{(1)}$. We consider $n$ i.i.d. random points $X_1,\ldots,X_n$ uniformly distributed on $\partial K$, where $n$ is a positive integer. Let $u\in S^{d-1}$ and $0\leq\varepsilon\leq r$. Then, the probability content of $C_K(u,\varepsilon)$, with respect to $\PP_{\partial K}$, is the ratio between the surface area of $\partial K\cap C_K(u,\varepsilon)$ and that of $\partial K$. By the $r$-rolling condition, the surface area of $\partial K\cap C_K(u,\varepsilon)$ is greater or equal to that of a spherical cap of radius $r$ and height $\varepsilon$. If we denote by $A_d$ the surface area of the unit sphere $S^{d-1}$, the surface area $A(r,\varepsilon)$ of such a spherical cap satisfies
\begin{align*}
	A(r,\varepsilon) & = \frac{1}{2}A_dr^{d-1}\int_0^{\frac{\varepsilon(2r-\varepsilon)}{r^2}}t^\frac{d-3}{2}(1-t)^{-1/2} dt \\
	& \geq \frac{1}{2}A_dr^{d-1}\int_0^{\frac{\varepsilon}{r}}t^\frac{d-3}{2} dt \\
	& \geq A_dr^\frac{d-1}{2}\varepsilon^\frac{d-1}{2}
\end{align*}
In addition, since $K$ is convex and is included in $B_d(0,1)$, the surface area of its boundary is bounded from above by that of $S^{d-1}$, which we denoted by $A_d$. In turn, 
\begin{equation*}
	\PP_{\partial K}\left[C_K(u,\varepsilon)\right]\geq r^\frac{d-1}{2}\varepsilon^\frac{d-1}{2},
\end{equation*}
and therefore, $(\PP_{\partial K},K)$ belongs to the class $\displaystyle{\mathcal M\left(\frac{d-1}{2},r^\frac{d-1}{2},r\right)}$. Hence, as a consequence of Theorem \ref{theorem21}, we have the following result for the convex hull of independent random points uniformly distributed on the boundary of a smooth convex body:

\begin{theorem}
	Let $d\geq 2$, $n$ be positive integers and $0<r\leq 1$. Define $\displaystyle{\tau_4=\max\left(1,\frac{2d}{C_\frac{d-1}{2}(d-1)r^\frac{d-1}{2}}\right)}$, $\displaystyle{a_n=\left(\frac{\tau_4\ln n}{n}\right)^\frac{2}{d-1}}$ and $\displaystyle{b_n=n^{-\frac{2}{d-1}}}$.
	The random polytope $\widehat K_n$ satisfies the following uniform deviation inequality on the class $\mathcal K_{d,r}^{(1)}$: For all nonnegative number $x$ satisfying $\displaystyle{a_n+b_n x\leq r}$
	$$\sup_{K\in\mathcal K_{d,r}^{(1)}} \PP_{\partial K}\left[d_H(\widehat {K_n},K)\geq 2a_n + 2b_n x\right] \leq 12^d\exp\left(-C_\frac{d-1}{2}r^\frac{d-1}{2} x^\alpha\right).$$
\end{theorem}

Uniform moment inequalities follow from this theorem:

\begin{corollary}\label{corollary1}
	Let $d\geq 2$ be a positive integer and $r\in (0,1]$. Then, for all real number $q\geq 1$,
	$$\sup_{K\in\mathcal K_{r,d}^{(1)}} \E_{\partial K}\left[d_H(\widehat K_n,K)^q\right]=O\left(\left(\frac{\ln n}{n}\right)^\frac{2q}{d-1}\right).$$
\end{corollary}










\begin{remark}
	Section \ref{UnifCase0} is devoted to uniform probability measures, either in a convex body $K$, or on its boundary. In both cases, the uniform probability measure admits a constant density $f$, with respect to either the Lebesgue measure or the surface area measure of $\partial K$. From the proofs, it is clear that our results extend to the case when $0<a\leq f(x)\leq b$ for all $x$ in the support of $\mu$ (either $K$, or $\partial K$), where $a$ and $b$ are two fixed positive numbers. The rates of convergence, in terms of $n$, are still the same and only the constants are modified, depending on $a$ and $b$.
\end{remark}



\section{Proofs}

We start with the following lemma, which is directly inspired by Lemma 5.2 in \cite{FresenVitale2014}. %If $\delta$ is a positive number and $(S,\rho)$ is a pseudo metric space, with $\rho$ satisfying all axioms of a distance but possibly symmetry, we call a left-sided (resp. right-sided) $\delta$-net of $(S,\rho)$ any subset $\mathcal N_\delta$ of $S$ such that for all $u\in S$, there exists $u_0\in \mathcal N$ with $\rho(u,u_0)\leq \delta$ (resp. $\rho(u_0,u)\leq \delta$).

\begin{lemma} \label{lemma1}
Let $K\in\mathcal K_d$ and $\delta$ be a positive real number. There exists a subset $\mathcal N_\delta$ of $\partial K$, satisfying the following: 
\begin{itemize}
	\item The cardinality of $\mathcal N_\delta$ is not larger than $\displaystyle{\left(\frac{3}{\delta}\right)^d}$;
	\item For all $u\in \partial K$, there exist two sequences $(u_j)_{j\geq 0}\subseteq \mathcal N_\delta$ and $(\delta_j)_{j\geq 1}\subseteq \R$ such that the following holds:
	\begin{itemize}
		\item $\forall j\geq 1, 0\leq \delta_j\leq \delta^j$ and
		\item $\displaystyle{u=u_0-\sum_{j=1}^\infty \delta_j u_j}$.
	\end{itemize}
\end{itemize}
\end{lemma}


\paragraph{Proof of Theorem \ref{theorem21}}

Let $(\mu,K)\in\mathcal M(\alpha,L,\varepsilon_0)$.
Let $\varepsilon\in [0,\varepsilon_0]$ and $\delta=\varepsilon/4$.
For all $u\in\mathcal S^{d-1}$, the following statements are equivalent:
\begin{itemize}
	\item $h_{\widehat K_n}(u) \leq h_K(u)-\varepsilon$
	\item All the points $X_1,\ldots,X_n$ are outside $C_K(u,\varepsilon)$.
\end{itemize}
Hence, 
\begin{align} \label{step1}
	\mu\left[h_{\widehat K_n}(u)\leq h_K(u)-\varepsilon\right] & = \mu\left[\forall i=1,\ldots,n, X_i\notin C_K(u,\varepsilon)\right] \nonumber \\
	& = \left(1-\mu\left(C_K(u,\varepsilon)\right)\right)^n \nonumber \\
	& \leq \exp\left(-Ln\varepsilon^\alpha\right).
\end{align}
Let $\mathcal N_\delta$ be a subset of $S^{d-1}$ satisfying Lemma \ref{lemma1}, for the unit Euclidean ball. Let us denote by $A$ the event $\{\forall u\in\mathcal N_\delta, h_{\widehat K_n}(u)> h_K(u)-\varepsilon\}$. By \eqref{step1} and the union bound, 
\begin{equation} \label{step2}
	\mu(A)\geq 1- \left(\frac{3}{\delta}\right)^d\exp\left(-Ln\varepsilon^\alpha\right).
\end{equation}
Let $A$ hold and $u\in S^{d-1}$. By Lemma \ref{lemma1}, we can write $\displaystyle{u=u_0+\sum_{j=1}^\infty \delta_j u_j}$ where $\displaystyle{(u_j)_{j\geq 0}\subseteq \mathcal N_\delta}$ and $0\leq\delta_j\leq \delta^j, \forall j\geq 1$.
Note that $\mu$-almost surely, $\widehat K_n\subseteq K\subseteq B_d(0,1)$, hence $h_{\widehat K_n}(u)\leq h_K(u)\leq 1, \forall u\in S^{d-1}$. Thus,
\begin{align} \label{step3}
	h_{\widehat K_n}(u) & = h_{\widehat K_n}(u_0+\sum_{j=1}^\infty \delta_j u_j) \nonumber \\
	& \geq  h_{\widehat K_n}(u_0)-\sum_{j=1}^\infty \delta^j h_{\widehat K_n}(-u_j) \mbox{ by \eqref{prop1} and \eqref{prop2}} \nonumber \\
	& > h_K(u_0)-\varepsilon-\frac{\delta}{1-\delta} \nonumber \\
	& > h_K(u)-\sum_{j=1}^\infty \delta^j h_K(u_j) - \varepsilon-\frac{\delta}{1-\delta} \mbox{ again by \eqref{prop1} and \eqref{prop2}} \nonumber \\
	& > h_K(u)-\varepsilon-\frac{2\delta}{\delta-1} \nonumber \\
	& > h_K(u)-2\varepsilon,
\end{align}
since $\delta=\varepsilon/4 \leq \varepsilon_0/4\leq 1/2$.

Hence, by \eqref{step2} and \eqref{step3},
\begin{align} \label{step4}
	\mu\left[d_H(\widehat K_n,K)\geq 2\varepsilon\right] & = \mu\left[\exists u\in S^{d-1}, h_{\widehat K_n}(u)\leq h_K(u)-\varepsilon\right] \nonumber \\
	& \leq \left(\frac{12}{\varepsilon}\right)^d\exp\left(-Ln\varepsilon^\alpha\right) \nonumber \\
	& \leq 12^d\exp\left(-Ln\varepsilon^\alpha -d\ln\varepsilon\right).
\end{align}
By setting $\varepsilon=a_n+b_n x$ for some nonnegative number $x$, where $a_n$ and $b_n$ are defined in Theorem \ref{theorem21}, we have that 
$$\varepsilon^\alpha\geq C_\alpha \left(\frac{\tau_1\ln n}{n} + \frac{x^\alpha}{n}\right),$$
and $$\ln \varepsilon \geq \ln a_n \geq -\frac{\ln n}{\alpha}.$$
The conclusion of Theorem \ref{theorem21} follows. \hfill $\square$


\paragraph{Proof of Corollary \ref{corollary2}}

Let $Z$ be a nonnegative random variable and $q$ be a positive number. Then, by Fubini's theorem,
$$\E[Z^q]=q\int_0^\infty t^{q-1}\PP[Z\geq t]dt.$$
Let us apply this equality to $Z=d_H(\widehat K_n,K)$ (which we denote by $d_H$ for the sake of simplicity) and $q\geq 1$. Since $d_H(\widehat K_n,K)\leq 2$ $\mu$-almost surely,
\begin{align}\label{step31}
	\E_\mu[d_H&(\widehat K_n,K)^q] & \nonumber \\
	& = q\int_0^\infty t^{q-1}\mu\left[d_H\geq t\right] dt  \nonumber \\
	& = q\int_0^{2a_n}  t^{q-1}\mu\left[d_H\geq t\right] dt + q\int_{2a_n}^{2\varepsilon_0} t^{q-1}\mu\left[d_H\geq t\right]dt \nonumber \\
	& \hspace{2cm} + q\int_{2\varepsilon_0}^2 t^{q-1}\mu\left[d_H\geq t\right]dt.
\end{align}
In the first integral, let us bound the probability by 1. In the second and third integrals, we perform the change of variable $t=2a_n +2b_nx$. Then, by Theorem \ref{theorem21} and the remark that follows it, \eqref{step31} becomes:
\begin{align}\label{step32}
	\E_\mu[d_H& (\widehat K_n,K)^q] \nonumber \\
	& \leq (2a_n)^q + 2q b_n\int_0^{(\varepsilon_0-a_n)b_n^{-1}} (2a_n +2b_nx)^{q-1}\mu\left[d_H\geq 2a_n+2b_n x\right]dx \nonumber \\
	& \hspace{15mm} + 2q b_n\int_{(\varepsilon_0-a_n)b_n^{-1}}^{(1-a_n)b_n^{-1}} (2a_n +2b_nx)^{q-1}\mu\left[d_H\geq 2a_n+2b_n x\right]dx  \nonumber \\
	& \leq (2a_n)^q +  q b_n\int_0^{(\varepsilon_0-a_n)b_n^{-1}}(2a_n+2b_n x)^{q-1}12^d\exp\left(-C_\alpha L x^\alpha\right)dx \nonumber \\
	& \hspace{15mm} + q 2^{q-1}|1-\varepsilon_0|b_n^{-1}12^d\exp\left(-C_\alpha L |1-\varepsilon_0|^\alpha b_n^{-\alpha}\right). \nonumber \\
\end{align}
In the second term, we bound $(a_n +b_n x)^{q-1}$ by $2^{q-1}a_n^{q-1} +b_n^{q-1} x^{q-1}$, which yields
\begin{align} \label{step33}
	& \int_0^{(\varepsilon_0-a_n)b_n^{-1}}(2a_n+2b_n x)^{q-1}12^d\exp\left(-C_\alpha L x^\alpha\right)dx \nonumber \\
	& \hspace{4mm}\leq 12^d 4^{q-1}\left(a_n^{q-1}\int_0^{\infty}\exp\left(-C_\alpha L x^\alpha\right)dx + b_n^{q-1}\int_0^{\infty}x^{q-1}\exp\left(-C_\alpha L x^\alpha\right)dx \right).
\end{align}
Since $b_n=O(a_n)$, altogether, \eqref{step32} and \eqref{step33} yield Corollary \ref{corollary1}. \hfill $\square$


\paragraph{Proof of Theorem \ref{theorem2'}}

Let $(\mu,K)\in\mathcal M(\alpha,L,\varepsilon_0)$ and let $u\in S^{d-1}$. By \eqref{step1}, for all $\varepsilon\in [0,\varepsilon_0]$,
$$\mu\left[h_{\widehat K_n}(u)\leq h_K(u)-\varepsilon\right] \leq \exp\left(-Ln\varepsilon^\alpha\right).$$
For $\varepsilon\in (\varepsilon_0,2]$,
$$\mu\left[h_{\widehat K_n}(u)\leq h_K(u)-\varepsilon\right] \leq \exp\left(-Ln\varepsilon_0^\alpha \right),$$
since the left hand side is a nonincreasing function of $\varepsilon$ and if $\varepsilon > 2$,
$$\mu\left[h_{\widehat K_n}(u)\leq h_K(u)-\varepsilon\right]=0.$$
Hence, by a similar argument as in the proof of Corollary \ref{corollary2}, for all real number $k\geq 1$, there is some positive number $c_k$ that depends neither on $\mu, K$ nor on $u$ and such that
\begin{equation}\label{step2'1}
	\E_\mu\left[|h_K(u)-h_{\widehat K_n}(u)|^k\right] \leq c_kn^{-\frac{k}{\alpha}}.
\end{equation}
If $q\leq p$, Jansen's inequality applied to the concave function $\displaystyle{[0,\infty)\ni x\mapsto x^\frac{q}{p}}$ and the expectation operator $\E_\mu$ yields
\begin{align} \label{step2'1bis}
	\E_\mu\left[\|h_{\widehat K_n}-h_K\|_p^q\right] & = \E_\mu\left[\left(\int_{S^{d-1}}|h_K(u)-h_{\widehat K_n}(u)|^pd\sigma(u)\right)^{q/p}\right] \nonumber \\
	& \leq \E_\mu\left[\int_{S^{d-1}}|h_K(u)-h_{\widehat K_n}(u)|^pd\sigma(u)\right]^{q/p}.
\end{align}
By Fubini's theorem, which allows switching the expectation and the integral and by \eqref{step2'1} with $k=p$, \eqref{step2'1bis} yields
\begin{equation*}
	\E_\mu\left[\|h_{\widehat K_n}-h_K\|_p^q\right] \leq c_p^{q/p}n^{-\frac{q}{\alpha}},
\end{equation*}
which proves the theorem in the case $q\leq p$. If now $q>p$, the mapping $\displaystyle{[0,\infty)\ni x\mapsto x^\frac{q}{p}}$ is convex and Jensen's inequality applied to the operator $\int_{S^{d-1}}$ yields
\begin{equation*}
	\left(\int_{S^{d-1}}|h_K(u)-h_{\widehat K_n}(u)|^p\right)^{q/p} \leq \int_{S^{d-1}}|h_K(u)-h_{\widehat K_n}(u)|^q,
\end{equation*}
so again by Fubini's theorem and using \eqref{step2'1} with $k=q$,
\begin{equation*}
	\E_\mu\left[\|h_{\widehat K_n}-h_K\|_p^q\right] \leq c_qn^{-\frac{q}{\alpha}},
\end{equation*}
which ends the proof of the theorem. \hfill $\square$




\paragraph{Proof of Theorem \ref{theorem3}}

We generalise the method used in \cite{KorostelevTsybakov1994} in the planar case to any dimension. This is a standard method that was already exploited in \cite{KorostelevSimarTsybakov1995'}.
We fix $R\in(r,1]$ and set $G_0=B_d(0,R)$. Let $\delta$ be a positive and small enough real number. For $u\in S^{d-1}$, we define the set $G(u)$ as follows.
Let $\eta:\R\rightarrow\R$ be a given nonnegative function, twice continuously differentiable, such that 
\begin{itemize}
	\item $\forall x\in\R, |x|\geq 1 \Rightarrow \eta(x)=0$ and
	\item $\displaystyle{\max_{x\in\R} \eta(x)=\eta(0)=1}$.
\end{itemize}
For instance, one can take $\displaystyle{\eta(x)=e^4g(2x-1)g(2-2x), \forall x\in\R}$, where 
\begin{align*}
	g:\R& \rightarrow \R \\
	x & \mapsto \left\{
	\begin{array}{ll}
		\exp(-1/x)  & \mbox{if } x>0 \\
		0 & \mbox{otherwise.}
	\end{array}
\right.
\end{align*}
Let $H$ be the supporting hyperplane of $G$ at the point $Ru\in\partial G_0$. Identify this hyperplane with $\R^{d-1}$, with origin at the point $Ru$. Then, a parametrisation of $G_0$ is 
$$G_0=\left\{(t,y)\in H\times\R \hspace{2mm} / \hspace{2mm}|t|\leq R, \hspace{2mm}R-\sqrt{R^2-|t|^2}\leq y\leq R+\sqrt{R^2-|t|^2}\right\},$$
where we denote by $|\cdot|$ the Euclidean norm in $H$.
We define the set $G(u)$ by modifying the parametrisation of $\partial G_0$ in a small neighborhood of $Ru$:
\begin{align*}
	G(u)=\Big\{(t,y)\in H\times \R \hspace{2mm} / \hspace{2mm} & |t|\leq R, \\
	& R-\sqrt{R^2-|t|^2}+\alpha\delta^2\eta\left(\frac{2|t|}{R\delta}\right) \leq y\leq R+\sqrt{R^2-|t|^2}\Big\},
\end{align*}
where $\alpha$ is a positive number that can be tuned inependently of $\delta$ so that $G(u)\in\mathcal K_{r,d}$, for small enough $\delta$. Note that for all $u\in S^{d-1}, G(u)\subseteq G_0$ and
\begin{align}\label{step31}
	|G_0\backslash G(u)| & = \alpha\delta^2\int_{\R^d}\eta\left(\frac{2|t|}{R\delta}\right)dt \nonumber \\
	& = \frac{\alpha\delta^{d+1}R^{d-1}}{2^{d-1}}\int_{\R^d}\eta(|t|)dt \nonumber \\
	& = c\delta^{d+1},
\end{align}
for some positive constant $c$ that depends on $R$ and $d$ only. In addition, if $(u,u')\in S^{d-1}\times S^{d-1}$ is such that $\|u-u'\|\geq\delta$, 
\begin{equation} \label{step32}
	d_H\left(G(u),G(u')\right)=\alpha\delta^2.
\end{equation}
Let now $\mathcal N$ be a maximal $\delta$-packing of $S^{d-1}$, i.e., a finite subset of $S^{d-1}$ with maximal cardinality, satisfying 
$$\forall (u,v)\in\mathcal N, \|u-v\| <\delta \Rightarrow u=v.$$
Let us denote by $N$ its cardinality and by $u_1,\ldots,u_N$ its elements and, for $j=1,\ldots,N$, set $G_j=G(u_j)$. By a standard argument (e.g. \cite{KolomogorovTikhomirov1959}), $N\geq c\delta^{-d}$, for some positive constant $c$.
Now, by setting $\displaystyle{\delta=\left(\frac{\ln n}{n}\right)^\frac{1}{d+1}}$, we apply Lemma 1 in \cite{KorostelevSimarTsybakov1995'} to the sets $G_0,G_1,\ldots,G_N$, whose assumptions are satisfied thanks to \eqref{step31} and \eqref{step32} and this proves Theorem \ref{theorem3}. \hfill $\square$






\paragraph{Proof of Theorem \ref{theorem1}}

The proof of this theorem follows the same lines at that of Theorem \ref{theorem21}. Let $d\geq 1$, $r\in (0,1]$ and $K\in\mathcal K_{r,d}$. For notational convenience, we set $$\widetilde r=r\left(\frac{|K|}{\beta_d}\right)^{1/d}.$$ Let $n$ be a positive integer and $X, X_1, X_2, \ldots, X_n$ be $n+1$ i.i.d. random points uniformly distributed in $K$. Without loss of generality, one can assume that $0$ is an interior point of $K$ and $B_d(0,\widetilde r)\subseteq K$. Indeed, since $K\in\mathcal K_{r,d}$, there exists a point $a\in K$ such that $B_d(a,\widetilde r)\subseteq K$. One can then replace $K$ with $K-a$ and not change the distribution of $d_H(\widehat K_n,K)$. Hence, for all $u\in S^{d-1}, h_K(u)\geq \widetilde r$ and
\begin{align*}
	d_L(\widehat K_n,K) & \leq \inf\{\varepsilon>0 / (1-\varepsilon)K\subseteq \widehat K_n\subseteq (1+\varepsilon)K\} \\
	& = \inf\{\varepsilon>0 / (1-\varepsilon)K\subseteq \widehat K_n\} \\
	& = \inf\{\varepsilon>0 / \forall u\in S^{d-1}, (1-\varepsilon)h_K(u)\subseteq h_{\widehat K_n}(u)\}.
\end{align*}

%Note that $\widehat K_n\subseteq K$ almost surely, yielding $h_{\widehat K_n}(u)\leq h_K(u)$, for all $u\in\R^d$.

Let $\varepsilon\in (0,1]$ and $u\in S^{d-1}$. By the $\widetilde r$-rolling condition, we have, similarly to \eqref{radiuscap},
\begin{align*}
	|C_K(u,\varepsilon \widetilde r)| & = \int_0^{\varepsilon \widetilde r} \sqrt{x(2\widetilde r-x)}^{d-1}\beta_{d-1}dx \\
	& \geq \beta_{d-1}\widetilde r^\frac{d-1}{2}\int_0^{\varepsilon \widetilde r} x^\frac{d-1}{2}dx  \\
	& \geq \frac{2\beta_{d-1}\widetilde r^d}{d+1}\varepsilon^\frac{d+1}{2}  \\
	& = \frac{2\beta_{d-1} r^d |K|}{\beta_d(d+1)}\varepsilon^\frac{d+1}{2}.
\end{align*}
Hence, if $\displaystyle{\eta=\frac{2\beta_{d-1} r^d}{\beta_d(d+1)}}$,
\begin{align*}
	\PP\left[\frac{h_{\widehat K_n}(u)}{h_K(u)}\leq 1-\varepsilon\right] & = \PP\left[h_{\widehat K_n}(u) \leq h_K(u)-\varepsilon h_K(u)\right]  \\
	& \leq \PP\left[h_{\widehat K_n}(u) \leq h_K(u)-\varepsilon \widetilde r\right]  \\
	& = \left(1-\frac{|C_K(u,\varepsilon \widetilde r)|}{|K|}\right)^n  \\
	& \leq \exp\left(- \eta  n\varepsilon^\frac{d+1}{2}\right).
\end{align*}
It follows, by positive homogeneity of support functions (see \eqref{prop1}), that for all $u\in\R^d\backslash\{0\}$,
\begin{equation} \label{step113}
	\PP\left[\frac{h_{\widehat K_n}(u)}{h_K(u)}\leq 1-\varepsilon\right] \leq \exp\left(- \eta n\varepsilon^\frac{d+1}{2}\right).
\end{equation}

We now introduce a finite subset of $\partial (K^\circ)$ satisfying the requirements of Lemma \ref{lemma1}, then apply \eqref{step113} to each of its elements and use a union bound inequality. By an analytic argument, we will then be able to bound from above the probability that the inequalities $\displaystyle{\left\{\frac{h_{\widehat K_n}(u)}{h_K(u)}\leq 1-\varepsilon\right\}}$ hold simultaneously for all $\displaystyle{u\in\partial (K^{\circ})}$ and, as a consequence of positive homogeneity of support functions, for all $u\in S^{d-1}$.




Set $\delta=\varepsilon/2$ and let $\mathcal N_\delta$ be a subset of $\partial (K^\circ)$ satisfying the requirements of Lemma \ref{lemma1}. Applying \eqref{step113} to each element of $\mathcal N_\delta$ and using a union bound inequality, yield that with probability at least $\displaystyle{1-\left(\frac{6}{\varepsilon}\right)^d\exp\left(- \eta n\varepsilon^\frac{d+1}{2}\right)}$, 
\begin{equation} \label{event1}
	\forall u\in\mathcal N_\varepsilon, \frac{h_{\widehat K_n}(u)}{h_K(u)} > 1-\varepsilon.
\end{equation}
Let us assume that Event \eqref{event1} holds and let $u$ be any element of $\partial (K^\circ)$. Write $\displaystyle{u=u_0-\sum_{j=1}^\infty \varepsilon_j u_j}$, as in Lemma \ref{lemma1}. Using \eqref{prop1}, \eqref{prop2} and 
\eqref{prop3}, 
\begin{equation} \label{step114}
	h_{\widehat K_n}(u)\geq h_{\widehat K_n}(u_0)-\sum_{j=1}^\infty \delta_j h_{\widehat K_n}(u_j).
\end{equation}
In addition, for all nonnegative integer $j$, $h_K(u_j)(1-\varepsilon)\leq h_{\widehat K_n}(u_j) \leq h_K(u_j)$. Since $0\in int(K)$ and $u_j\in\partial (K^\circ)$, $h_K(u_j)=\|u_j\|_{K^\circ}=1$ and the following is true, for all $u\in\partial (K^\circ)$:
\begin{align} \label{step115}
	h_{\widehat K_n}(u) & > 1-\varepsilon -\sum_{j=1}^\infty \delta^j \nonumber \\
	& \geq 1-\varepsilon-\frac{\delta}{1-\delta} \geq 1-2\varepsilon.
\end{align}
Finally, note that $0\in int(K^\circ)$, for $K$ is bounded. So, for all $u\in S^{d-1}$, there is a positive $\lambda$ for which $\lambda u\in\partial (K^\circ)$ and 
\begin{equation*}
	\frac{h_{\widehat K_n}(u)}{h_K(u)}=\frac{h_{\widehat K_n}(\lambda u)}{h_K(\lambda u)} > 1-2\varepsilon.
\end{equation*}
Hence, we showed that with probability at least $\displaystyle{1-\left(\frac{6}{\varepsilon}\right)^d\exp\left(- \eta n\varepsilon^\frac{d+1}{2}\right)}$, 
$$\forall u\in S^{d-1}, \frac{h_{\widehat K_n}(u)}{h_K(u)} > 1-2\varepsilon.$$
It follows that 
$$d_L(\widehat K_n,K)< 2\varepsilon.$$
Hence, we showed that
\begin{equation} \label{step116}
	\PP\left[d_L(\widehat K_n,K)\geq 2\varepsilon \right] \leq 6^d\exp\left(- \eta n\varepsilon^\frac{d+1}{2}-d\ln\varepsilon\right),
\end{equation}
which yields Theorem \ref{theorem1} by setting $\varepsilon=a_n+b_n x$. \hfill $\square$






















\bibliographystyle{plain}
\bibliography{Biblio}

\end{document} 












Article2.bbl
\begin{thebibliography}{10}

\bibitem{BoroczkyFodorReitznerVigh2009}
K.~J. Böröczky, F.~Fodor, M.~Reitzner, and V.~Vigh.
\newblock Mean width of random polytopes in a reasonably smooth convex body.
\newblock {\em Journal of Multivariate Analysis}, 100:2287--2295, 2009.

\bibitem{Barany1989}
I.~Bàràny.
\newblock Intrinsic volumes and f-vectors of random polytopes.
\newblock {\em Math. Ann.}, 285:671--699, 1989.

\bibitem{BaranyBuchta1993}
I.~Bàràny and C.~Buchta.
\newblock Random polytopes in a convex polytope, independence of shape, and
  concentration of vertices.
\newblock {\em Math. Ann.}, 297:467--497, 1993.

\bibitem{BaranyLarman1988}
I.~Bàràny and D.~G. Larman.
\newblock Convex bodies, economic cap coverings, random polytopes.
\newblock {\em Mathematika}, 35:274--291, 1988.

\bibitem{Brunel2013''}
V.-E. Brunel.
\newblock Adaptive estimation of convex and polytopal density support.
\newblock {\em To appear in Probability and Related Fields}, 2014.

\bibitem{Brunel13''}
V.-E. Brunel.
\newblock A universal deviation inequality for random polytopes.
\newblock {\em submitted,
  \href{http://arxiv.org/pdf/1311.2902v1.pdf}{arXiv:1311.2902}}, 2014.

\bibitem{DumbgenWalther1996}
L.~Dümbgen and G.~Walther.
\newblock Rates of convergence for random approximations of convex sets.
\newblock 1996.

\bibitem{FresenVitale2014}
D.~Fresen and R.~Vitale.
\newblock Concentration of random polytopes around the expected convex hull.
\newblock {\em Electron. Commun. Probab.}, 19:1--8, 2014.

\bibitem{Gayraud1997}
G.~Gayraud.
\newblock Estimation of functionals of density support.
\newblock {\em Mathematical Methods of Statistics}, 6:26--47, 1997.

\bibitem{GlasauerSchneider1996}
S.~Glasauer and R.~Schneider.
\newblock Asymptotic approximation of smooth convex bodies by polytopes.
\newblock {\em Forum Mathematicum}, 8:363--377, 1996.

\bibitem{Groemer1974}
H.~Groemer.
\newblock On the mean value of the volume of a random polytope in a convex set.
\newblock {\em Arch. Math.}, 25:86--90, 1974.

\bibitem{KolomogorovTikhomirov1959}
A.~N. Kolmogorov and V.~M. Tikhomirov.
\newblock $\varepsilon$-entropy and $\varepsilon$-capacity of sets in function
  spaces (in russian).
\newblock {\em Uspekhi Mat. Nauk}, 14:3--86, 1959.

\bibitem{KorostelevSimarTsybakov1995'}
A.~P. Korostelev, L.~Simar, and A.~B. Tsybakov.
\newblock On estimation of monotone boundaries.
\newblock {\em The Annals of Statistics}, 23:476--489, 1995.

\bibitem{KorostelevTsybakov1994}
A.~P. Korostelev and A.~B. Tsybakov.
\newblock Asymptotic efficiency in estimation of a convex set (in russian).
\newblock {\em Problems of Information Transmission}, 30:317--327, 1994.

\bibitem{Muller1989}
J.~Müller.
\newblock On the mean width of random polytopes.
\newblock {\em Probability Theory and Related Fields}, 82:33--37, 1989.

\bibitem{Molchanov2005}
I.~Molchanov.
\newblock {\em Theory of Random Sets}.
\newblock Springer Verlag, 2005.

\bibitem{Pateiro2008}
B.~Pateiro-Lopez.
\newblock Set estimation under convexity type restrictions.
\newblock {\em
  \href{http://eio.usc.es/pub/pateiro/files/THESIS\_BeatrizPateiroLopez.pdf}{PhD
  Thesis}}, 2008.

\bibitem{Schneider1987}
R.~Schneider.
\newblock Approximation of convex bodies by random polytopes.
\newblock {\em Aequationes Mathematicae}, 32:304--310, 1987.

\bibitem{Schneider2004}
R.~Schneider.
\newblock Discrete aspects of stochastic geometry.
\newblock {\em in Handbook of discrete and computational geometry}, pages
  255--278, 2004.

\bibitem{SchneiderWieacker1980}
R.~Schneider and J.A. Wieacker.
\newblock Random polytopes in a convex body.
\newblock {\em Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte
  Gebiete}, 52:69--73, 1980.

\bibitem{Walther1999}
G.~Walther.
\newblock On a generalization of blaschke’s rolling theorem and the smoothing
  of surfaces.
\newblock {\em Math. Methods Appl. Sci.}, 22:301--316, 1999.

\end{thebibliography}
