Asymptotic expected $T$-functionals of random polytopes
with applications to $L_{p}$ surface areas

Random polytopes are a cornerstone of stochastic and integral geometry. They connect convex geometry and probability, and have a number of applications in computer science, statistics and machine learning theory. There is a vast literature on the subject of random polytopes, and we refer the reader to the survey articles [2, 11, 22] and the references therein.

Random polytopes generated as the convex hull of independent and identically distributed (i.i.d.) points sampled from the Euclidean unit ball or the Euclidean unit sphere in $\mathbb{R}^{n}$ according to the respective uniform distribution are important models that have been studied extensively in stochastic geometry. For the Euclidean ball, Wieacker [27] extended the results of Rényi and Sulanke [23] to $\mathbb{R}^{n}$. He obtained asymptotic formulas for the expected volume and expected surface area of a random polytope inscribed in a ball, and introduced what is known today as the $T$-functional $T_{a,b}^{n,k}(Q)$ of a polytope $Q$ in $\mathbb{R}^{n}$. It is defined as

where $a,b\geq 0$ are parameters, $\mathcal{F}_{k}(Q)$ stands for the set of $k$-faces of $Q$ for $k\in\{0,1,\ldots,n\}$, $o$ stands for the origin of $\mathbb{R}^{n}$ and $\operatorname{dist}(o,\operatorname{aff}(F))=\min\{\|x\|:x\in\operatorname{aff}(F)\}$ is the Euclidean distance from $o$ to the affine hull $\operatorname{aff}(F)$ of $F$. In particular, we notice that $T_{0,0}^{n,k}(Q)$ is the number of $k$-dimensional faces of $Q$ and $T_{0,1}^{n,k}(Q)$ is the $k$-content of the union of all $k$-faces of $Q$, whereas ${1\over n}T_{1,1}^{n,n-1}(Q)$ coincides with the volume of $Q$ as long as $Q$ contains the origin in its interior. Later on, Affentranger [1] described for $k=n-1$ and general parameters $a,b\geq 0$, the asymptotic behavior, as $N\to\infty$, of the expected $T$-functional of the convex hull of $N$ i.i.d. random points distributed according to a so-called beta distribution in the $n$-dimensional unit ball (so-called beta polytopes). We recall that the beta distribution with parameter $\beta>-1$ in the $n$-dimensional Euclidean unit ball $B_{n}$ has Lebesgue density

For example, choosing $\beta=0$ we obtain the uniform distribution on $B_{n}$, while the weak limit as $\beta\to-1^{+}$ corresponds to the uniform distribution on $\partial B_{n}$, the $(n-1)$-dimensional unit sphere. An exact formula for the expected $T$-functional $\mathbb{E}[T_{a,b}^{n,n-1}(P_{n,N}^{\beta})]$ of a beta polytope $P_{n,N}^{\beta}$, defined as the convex hull of $N\geq n+1$ i.i.d. random points distributed with respect to the density $f_{n,\beta}$, was provided by Kabluchko, Temesvari and Thäle [15]:

where

and $\mathbb{E}_{\beta}[\mathcal{V}_{n,n-1}^{b+1}]$ is the moment of order $b+1$ of the volume of the $(n-1)$-dimensional random beta simplex $P_{n-1,n}^{\beta}$, whose value can be expressed in terms of gamma functions (see [15, Proposition 2.8]). Formally putting $\beta=-1$, this formula also covers the case of the convex hull of $N\geq n+1$ i.i.d. uniform random points on the boundary $\partial B_{n}$ of $B_{n}$. The expected $T$-functional has further been determined explicitly for beta’ polytopes [15] and Gaussian polytopes [13], as well as for beta-star polytopes [7] and convex hulls of Poisson point processes [14]. The corresponding results have also found applications to stochastic geometry models in spherical and hyperbolic spaces.

In this article, we determine precise asymptotic formulas for the expected $T$-functional of an inscribed random polytope generated by i.i.d. points selected according to a general continuous positive density function on the Euclidean unit sphere or unit ball in $\mathbb{R}^{n}$. We focus on the case $k=n-1$ of the $T$-functional, in which case the summation in the definition ranges over the set of facets $\mathcal{F}_{n-1}(Q)$ of $Q$. For a polytope $Q$ in $\mathbb{R}^{n}$, we thus denote $T_{a,b}(Q):=T_{a,b}^{n,n-1}(Q)$. As already pointed out above, the case $k=n-1$ gives rise to a number of important functionals of polytopes. For example:

• •

  $T_{0,0}(Q)=|\mathcal{F}_{n-1}(Q)|$ is the number of facets of $Q$;

• •

  $T_{0,1}(Q)=\mu_{\partial Q}(\partial Q)$ is the surface area (i.e., $(n-1)$-dimensional Hausdorff measure) of $Q$;

• •

  $\tfrac{1}{n}T_{1,1}(Q)=\operatorname{vol}_{n}(Q)$ is the volume of $Q$, if $Q$ contains the origin in its interior.

To this list we can also add what is known as the $L_{p}$ surface area of a polytope $Q$ containing the origin in its interior, which for $p\in\mathbb{R}$ is defined as

For $p>1$, Lutwak [18] defined the $L_{p}$ surface area measure of a general convex body in $\mathbb{R}^{n}$ which contains the origin in its interior, and formulated and studied the famous $L_{p}$ Minkowski problem. This problem asks for necessary and sufficient conditions on a finite Borel measure $\mu$ on the sphere $\partial B_{n}$ so that $\mu$ is the $L_{p}$ surface area of some convex body $K$ in $\mathbb{R}^{n}$. The important special case when $K$ is a polytope is called the discrete $L_{p}$ Minkowski problem, and for more background we refer the reader to [12, 25, 26, 29] and the references therein.

The remaining parts of this paper are structured as follows. In Section 1.2, we present our general result on the expected $T$-functional. In Section 1.3, we discuss the special case of the $L_{p}$ surface area, followed by an application to best approximation in Section 1.4. Section 2 collects some preliminary geometric lemmas, and in Section 3 we present the proof of our main result.

Our main result is an asymptotic description of the expected $T$-functional of the convex hull of $N$ i.i.d. random points distributed according to an arbitrary positive and continuous density function on the sphere, as $N\to\infty$, for arbitrary parameter values $a,b\geq 0$. We would like to highlight that such a result is distinguished from those in [1, 15, 20] as we consider densities which are not necessarily rotationally invariant. In fact, choosing the uniform density, $k=n-1$ and $a=b=1$, our result reduces to that of [20, Theorem 2] or [1, Theorem 5] (choosing $i=0$ there), while the exact formula for the expected $T$-functional of a random beta polytope with general parameters $a,b\geq 0$ can be found in [15, Theorem 2.13].

In what follows, for $k\in\mathbb{N}$ we shall use the notation $\mu_{\partial B_{k}}$ to denote the $(k-1)$-dimensional spherical Lebesgue measure on the $(k-1)$-dimensional unit sphere $\partial B_{k}$, and we indicate the $k$-dimensional Lebesgue measure by $\operatorname{vol}_{k}$.

In this section, we specialize Theorem 1.1 to discuss the $L_{p}$ surface area difference $\Delta_{S_{p}}(B_{n},Q_{n,N}^{f})$ of the ball and a random inscribed polytope $Q_{n,N}^{f}$ that contains the origin in its interior. It is defined as

where we recall the definition of the $L_{p}$ surface area from (1). In fact, choosing $a=1-p$ with $p\in(-\infty,1]$ and $b=1$, we arrive at the following result.

Let $f_{\rm unif}:=\mu_{\partial B_{n}}(\partial B_{n})^{-1}\mathbbm{1}_{\partial B_{n}}$ denote the uniform density on $\partial B_{n}$. Following [24], we show that the uniform density minimizes the constant in the right-hand side of Corollary 1.4, which we denote by $c_{\rm bd}(n,p,f)$. Since $\int_{\partial B_{n}}f(x)\,d\mu_{\partial B_{n}}(x)=1$, we can write

Applying Hölder’s inequality to the functions $f_{1}(x)=f(x)^{-\frac{2}{n+1}}$, $f_{2}(x)=f(x)^{\frac{2}{n+1}}$, and with the exponents $p^{\prime}=\frac{n+1}{n-1}$ and $q^{\prime}=\frac{n+1}{2}$, we derive that

Therefore,

It follows that for any density $f$ on the unit sphere $\partial B_{n}$ and any $p\in(-\infty,1]$,

which means that the minimizing density is the uniform one, independently of $p$. Hence for every $p\in(-\infty,1]$ and any positive continuous density $f$ on $\partial B_{n}$, we have

as $N\to\infty$. In an asymptotic sense, this is a necessary condition for the random variable $S_{p}(Q_{n,N}^{f_{\rm unif}})$ to second-order stochastically dominate $S_{p}(Q_{n,N}^{f})$.

For $N\geq n+1$, let $\mathscr{P}_{n,N}^{\rm in}$ denote the set of all polytopes inscribed in $B_{n}$ with at most $N$ vertices and which contain the origin in their interiors. It follows from a compactness argument that for any fixed $p\in[0,1]$, there exists a best-approximating polytope which achieves the minimum $L_{p}$ surface area difference

Moreover, if $Q\in\mathscr{P}_{n,N}^{\rm in}$ and $p\in[0,1]$, then by the cone-volume formula we have

where $\mu_{\partial Q}(\partial Q)$ denotes the $(n-1)$-dimensional Hausdorff measure of $\partial Q$. Hence,

where $B_{n}\triangle Q=(B_{n}\cup Q)\setminus(B_{n}\cap Q)$ denotes the symmetric difference of $B_{n}$ and $Q$.

Interestingly, in high dimensions the random approximation of smooth convex bodies is asymptotically as good as the best approximation as $N\to\infty$, up to absolute constants; see [1, 3, 4, 5, 6, 9, 10, 16, 17, 20, 21, 24]. Choosing the minimizing density $f=f_{\rm unif}$ in Corollary 1.4, by Stirling’s inequality we derive

An interesting open question is to determine the optimal lower constant $\tilde{c}_{\rm bd}(n,p,f)$ (up to some factor $o_{n}(1)$) in the asymptotic lower bound

It follows from (4) and [4, Thm. 1 i)] that $\tilde{c}_{\rm bd}(n,p,f)\geq\frac{1}{2}(n-1)\mu_{\partial B_{n}}(\partial B_{n})\left(1+O\left(\frac{\ln n}{n}\right)\right)$.

In this section, we collect a number of geometric lemmas which will be used in the proof of Theorem 1.1 below. The first ingredient we need is the spherical Blaschke-Petkantschin formula from [19, Theorem 4], which has later found a far-reaching extension in [28].

The next result is a useful estimate of Schütt and Werner from [24, Lemma 3.12] involving the surface area and radius of a cap of the Euclidean ball.

Each pair of $u\in\partial B_{n}$ and $h\in[0,1]$ determines two caps of the sphere, one for each halfspace determined by the hyperplane $H=u^{\perp}+hu$. We select the halfspace $H^{-}$ that does not contain the polytope and focus on the cap $\partial B_{n}\cap H^{-}$. Then we let

denote the weighted surface area of the cap. Note that $\mathbb{P}_{f}(\partial B_{n}\cap H^{+})=1-s$. We use [21, Equation (71)] to merge [21, Lemma 6] with Lemma 2.2 in the following result.

The next result is due to Miles [19, Equation (72)] for integer moments, which was extended to moments of arbitrary nonnegative real order by Kabluchko, Temesvari and Thäle [15, Proposition 2.8] for general beta (and beta’) distributions in $\mathbb{R}^{n}$. The following formulation is the special case $\beta=-1$.

The next result gives estimates for moments of an $(n-1)$-dimensional random simplex with vertices distributed according to the restriction of the density $f$ to a great hypersphere of $\partial B_{n}$. For the second moment, a more general result for all sufficiently smooth convex bodies in $\mathbb{R}^{n}$ is due to Grote and Werner [8, Lemma 3.3]. Our proof is tailored towards the case of the sphere and, as a result, is much simpler.