# Random points are optimal
for the approximation of Sobolev functions

David Krieg111Institut für Analysis, Johannes Kepler Universität Linz, 4040
Linz, Austria<EMAIL_ADDRESS><EMAIL_ADDRESS> and Mathias
Sonnleitner∗

###### Abstract

We show that independent and uniformly distributed sampling points are as good
as optimal sampling points for the approximation of functions from the Sobolev
space $W_{p}^{s}(\Omega)$ on bounded convex domains
$\Omega\subset\mathbb{R}^{d}$ in the $L_{q}$-norm if $q<p$. More generally, we
characterize the quality of arbitrary sampling points $P\subset\Omega$ via the
$L_{\gamma}(\Omega)$-norm of the distance function
$\operatorname{dist}(\cdot,P)$, where $\gamma=s(1/q-1/p)^{-1}$ if $q<p$ and
$\gamma=\infty$ if $q\geq p$. This improves upon previous characterizations
based on the covering radius of $P$.

Keywords: sampling, rate of convergence, numerical integration, random
information, interior cone condition  MSC 2020: 41A25, 41A63, 62D05, 65D15,
65D30

Let $\Omega\subset\mathbb{R}^{d}$ be a bounded convex domain. We study the
problem of approximating a function $f$ from the Sobolev space
$W_{p}^{s}(\Omega)$ in the $L_{q}(\Omega)$-norm based on function values
$f(x_{j})$ on a finite set of sampling points $P=\\{x_{1},\ldots,x_{n}\\}$.
This makes sense if $s>d/p$, in which case $W_{p}^{s}(\Omega)$ is compactly
embedded into the space of continuous functions $C(\Omega)$. The minimal
worst-case error that can be achieved with the given sampling points is the
number

$e\big{(}P,W_{p}^{s}(\Omega)\hookrightarrow
L_{q}(\Omega)\big{)}:=\,\inf_{S_{P}}\,\sup_{\|f\|_{W_{p}^{s}(\Omega)}\leq
1}\|f-S_{P}(f)\|_{L_{q}(\Omega)},$

where the infimum is taken over all sampling operators of the form

$S_{P}\colon W_{p}^{s}(\Omega)\to L_{q}(\Omega),\qquad
S_{P}(f)=\varphi\big{(}f(x_{1}),\ldots,f(x_{n})\big{)}.$ (1)

In general, we admit arbitrary mappings $\varphi\colon\mathbb{R}^{n}\to
L_{q}(\Omega)$, but sometimes it may be preferable to allow only linear
mappings $\varphi$, in which case we write $e^{\rm lin}$ instead of $e$. We
also study the related problem of numerical integration on $\Omega$. To be
precise, we consider

$e\big{(}P,{\rm
INT},W^{s}_{p}(\Omega)\big{)}:=\inf_{S_{P}}\sup_{\|f\|_{W^{s}_{p}(\Omega)}\leq
1}\left|\int_{\Omega}f(x){\rm d}x-S_{P}(f)\right|,$ (2)

where the infimum is now taken over all sampling operators of the form

$S_{P}\colon W_{p}^{s}(\Omega)\to\mathbb{R},\qquad
S_{P}(f)=\varphi\big{(}f(x_{1}),\ldots,f(x_{n})\big{)}.$ (3)

In this case, it does not matter whether we allow arbitrary or only linear
mappings $\varphi\colon\mathbb{R}^{n}\to\mathbb{R}$ since the infimum
$e\big{(}P,{\rm INT},W^{s}_{p}(\Omega)\big{)}$ will be the same. This is a
classical result due to Smolyak and Bakhvalov, see e.g. Theorem 4.7 in [24].

There is a vast literature on the error of optimal sampling points. For
example, it is known that the rate of convergence of this error is

$e\big{(}n,W_{p}^{s}(\Omega)\hookrightarrow
L_{q}(\Omega)\big{)}:=\inf_{|P|\leq
n}e\big{(}P,W_{p}^{s}(\Omega)\hookrightarrow
L_{q}(\Omega)\big{)}\,\asymp\,n^{-s/d+(1/p-1/q)_{+}}$

for the approximation problem and

$e\big{(}n,{\rm INT},W^{s}_{p}(\Omega)\big{)}:=\inf_{|P|\leq n}e\big{(}P,{\rm
INT},W^{s}_{p}(\Omega)\big{)}\,\asymp\,n^{-s/d}$

for the integration problem, where $a_{+}:=\max\\{a,0\\}$, $a\in\mathbb{R}$,
and the infimum runs over all point sets $P\subset\Omega$ with at most $n$
points. The same holds for the error $e^{\rm lin}$ of linear algorithms. These
are classical results for special domains like the cube, see e.g. [5, Chapter
3] and [14, Chapter 6]. For general domains, we refer to Narcowich, Wendland
and Ward [21] as well as Novak and Triebel [22].

In this paper, however, we are not so much interested in optimal sampling
points. Although the question is quite interesting, we feel that there are
many applications where it is unrealistic to assume that we can choose the
sampling points at our convenience. It might rather be realistic to assume
that the points are independent random variables which are uniformly
distributed on the domain. That is, we get our data $f(x_{j})$ for random
parameters $x_{j}\in\Omega$ which are not under our control. But is this a
major drawback? Are random points significantly worse than optimal points?

It can be understood from [21, 22] that the optimal order of convergence may
be achieved with any set of sampling points that cover the domain well enough,
meaning that the volume of the largest empty ball amidst the point set is of
order $1/n$. In other words, the covering radius, which is the supremum of the
distance function

$\operatorname{dist}(\cdot,P)\colon\mathbb{R}^{d}\to[0,\infty),\qquad\operatorname{dist}(x,P):=\min_{y\in
P}\|x-y\|_{2}$

over $x\in\Omega$, i.e., the radius of the largest empty ball, has to be of
order $n^{-1/d}$. In this case, an optimal algorithm is given by moving least
squares, see e.g. Wendland [35]. In fact, it is quite common to use the
covering radius, which is also called mesh norm, to bound errors of sampling-
based algorithms, see also [2, 4, 9, 12, 20, 36] for example. Unfortunately,
random point sets do not have optimal covering properties since the volume of
the largest empty ball is of order $\log(n)/n$. On the other hand, _most_
empty balls are of order $1/n$ and one might think that a few larger gaps do
not matter if the error is measured in the $L_{q}$-norm for sufficiently small
$q$. We use a local version of Wendland’s result to show that this is indeed
true for any $q<p$. We obtain the following characterization of the error of
$L_{q}$-approximation and numerical integration.

######  Theorem 1.

Let $\Omega\subset\mathbb{R}^{d}$ be a bounded convex domain, $1\leq
p,q\leq\infty$ and $s\in\mathbb{N}$ with $s>d/p$. Then we have for any
nonempty and finite point set $P\subset\Omega$ the equivalences

$\displaystyle e^{\ast}\big{(}P,W^{s}_{p}(\Omega)\hookrightarrow
L_{q}(\Omega)\big{)}\,\asymp\,\begin{cases}\big{\|}\operatorname{dist}(\cdot,P)\big{\|}_{L_{\infty}(\Omega)}^{s-d(1/p-1/q)}&\text{if
}q\geq p,\vphantom{\bigg{|}}\\\
\big{\|}\operatorname{dist}(\cdot,P)\big{\|}_{L_{\gamma}(\Omega)}^{s}&\text{if
}q<p,\end{cases}$ (a) $\displaystyle e\big{(}P,{\rm
INT},W^{s}_{p}(\Omega)\big{)}\,\asymp\,e^{\ast}\big{(}P,W^{s}_{p}(\Omega)\hookrightarrow
L_{1}(\Omega)\big{)},$ (b)

where $e^{\ast}\in\\{e,e^{\rm lin}\\}$, $\gamma=s(1/q-1/p)^{-1}$ and the
implied constants are independent of $P$.

This shows that the covering radius is not the right quantity to characterize
the error in the case $q<p$, and in particular, for numerical integration. In
general, the assumption of a small covering radius is unnecessarily strong.
Instead, we get the following characterization of optimal point sets.

######  Corollary 1.

Let $\Omega\subset\mathbb{R}^{d}$ be a bounded convex domain, $1\leq
p,q\leq\infty$ and $s\in\mathbb{N}$ with $s>d/p$. Assume that for each
$n\in\mathbb{N}$ an $n$-point set $P_{n}\subset\Omega$ is given. These point
sets are asymptotically optimal, i.e.,

$e^{\ast}\big{(}n,W^{s}_{p}(\Omega)\hookrightarrow
L_{q}(\Omega)\big{)}\,\asymp\,e^{\ast}\big{(}P_{n},W^{s}_{p}(\Omega)\hookrightarrow
L_{q}(\Omega)\big{)},$

if and only if

$\|\operatorname{dist}(\cdot,P_{n})\|_{L_{\gamma}(\Omega)}\,\preccurlyeq\,n^{-1/d},$

where $\gamma=s(1/q-1/p)^{-1}$ for $q<p$ and $\gamma=\infty$ for $q\geq p$,
$e^{\ast}\in\\{e,e^{\rm lin}\\}$ and the implied constants are independent of
$n$.

Since any sequence of point sets satisfies
$\|\operatorname{dist}(\cdot,P_{n})\|_{L_{\gamma}(\Omega)}\succcurlyeq
n^{-1/d}$ for all $\gamma\in(0,\infty]$, see also (4), our condition of
optimality is equivalent to
$\|\operatorname{dist}(\cdot,P_{n})\|_{L_{\gamma}(\Omega)}\,\asymp\,n^{-1/d}$.
We emphasize that the main contribution of this paper is the characterization
in the case $q<p$. The case $q\geq p$ is included for completeness. The
results for $q<p$ seem to be novel already for $d=1$. To the authors, similar
results only have been known for the spaces $W_{\infty}^{s}(\Omega)$ with
$s\leq 2$, see Sukharev [30] and Pagès [26]. The latter author uses concepts
from the theory of quantization of measures, described for example in [13], in
which $L_{\gamma}(\mu)$-norms of $\operatorname{dist}(\cdot,P)$ are studied
extensively for general distributions $\mu$.

By Theorem 1b, we clearly get the same characterization for numerical
integration as for the problem of $L_{1}$-approximation. In a certain sense,
this characterization may serve as an asymptotic (and weighted) analogue in
(isotropic) Sobolev spaces to the connection between errors of quasi-Monte
Carlo rules in several other function spaces and various types of the
geometric notion of discrepancy as surveyed for example in [25, Section 9].

######  Remark 1 (More general domains).

In fact, the proof of Theorem 1 for $q\geq p$ works for all domains that
satisfy an interior cone condition (as considered in [21]) and which admit a
bounded linear extension operator ${\rm ext}\colon W^{s}_{p}(\Omega)\to
W^{s}_{p}(\mathbb{R}^{d})$ with ${\rm ext}(f)|_{\Omega}=f$ for all $f\in
W^{s}_{p}(\Omega)$. This includes all bounded Lipschitz domains (as considered
in [22]), see Lemmas 5 and 8. Our proof for $q<p$ additionally requires a
strong local interior cone condition as described in Lemma 6, which is implied
by the assumed convexity of the domain. However, we conjecture that also the
case $q<p$ may be extended (at least) to all bounded Lipschitz domains.

######  Remark 2 (More general spaces).

Theorem 1 may also be extended to more general function spaces, including
Sobolev-Slobodeckij spaces of fractional smoothness, Triebel-Lizorkin spaces,
Hölder-Zygmund spaces and Bessel potential spaces, see Section 4.

######  Remark 3 (Sobolev bounds).

The presentation of our results has a different scope than [21] where bounds
for Sobolev norms of functions with scattered zeros are given in terms of the
covering radius. Using our approach, it should be possible to replace the
covering radius there and also in the subsequent work on sampling inequalities
(see e.g. [2]) by an $L_{\gamma}$-norm of the distance function but we leave
this for future work.

Our result enables us to study the quality of random sampling points which
have almost optimal covering properties. In fact, we have the following
proposition.

######  Proposition 1.

Let $X_{1},X_{2},\ldots$ be independent and uniformly distributed random
vectors on a bounded convex domain $\Omega\subset\mathbb{R}^{d}$ and let
$0<\alpha<\infty$. Consider the random $n$-point set
$P_{n}=\\{X_{1},\ldots,X_{n}\\}$. Then

$\mathbb{E}\,\|\operatorname{dist}(\cdot,P_{n})\|_{L_{\gamma}(\Omega)}^{\alpha}\,\asymp\,\begin{cases}n^{-\alpha/d}&\text{if
}0<\gamma<\infty,\\\ n^{-\alpha/d}(\log n)^{\alpha/d}&\text{if
}\gamma=\infty.\end{cases}$

This immediately yields the following result on the quality of random sampling
points.

######  Corollary 2.

Let $X_{1},X_{2},\ldots$ be independent and uniformly distributed random
vectors on a bounded convex domain $\Omega\subset\mathbb{R}^{d}$, $1\leq
p,q\leq\infty$ and $s\in\mathbb{N}$ with $s>d/p$. Consider the random
$n$-point set $P_{n}=\\{X_{1},\ldots,X_{n}\\}$. Then

$\mathbb{E}\,e^{\ast}\big{(}P_{n},W_{p}^{s}(\Omega)\hookrightarrow
L_{q}(\Omega)\big{)}\,\asymp\,\begin{cases}e^{\ast}\big{(}n/\log
n,W^{s}_{p}(\Omega)\hookrightarrow L_{q}(\Omega)\big{)}&\text{if }q\geq p,\\\
e^{\ast}\big{(}n,W^{s}_{p}(\Omega)\hookrightarrow
L_{q}(\Omega)\big{)}&\text{if }q<p.\vphantom{\Big{|}}\end{cases}$

This means that random points are asymptotically optimal for
$L_{q}$-approximation on $W^{s}_{p}(\Omega)$ whenever $q<p$. In particular,
random points are optimal for the problem of multivariate integration on
$W^{s}_{p}(\Omega)$ for all $p>1$.

######  Remark 4 (Other Asymptotics).

Using Markov’s inequality one can conclude that the upper bounds in Corollary
2 hold with high probability. In fact, also almost sure results may be derived
from a result by Cohort [6], see Proposition 3.

######  Remark 5 (Applications).

Independent and identically distributed random sampling points are a typical
assumption in learning theory and uncertainty quantification. To a certain
extent, our result explains why the approximation methods that are considered
in these areas can be so successful. Of course, Theorem 1 may also serve to
study other distributions than the uniform distribution on the domain.

For $q\geq p$, random points are not optimal. We note, however, that we only
loose a logarithmic factor and that random information is still almost
optimal. For the cube, this was already observed in [16]. There, in Section
2.3, the case $q<p$ was stated as an open problem, which is resolved by
Corollary 2. Further recent results on the general question of the quality of
random information may be found in [15, 17, 18, 33]. We point to the fact that
there are also situations where random information is much worse than optimal
information, see [17, Section 6] for an example.

The rest of the paper is organized as follows. In Section 1 we introduce
notation and present some basic facts on domains, polynomial reproduction and
Sobolev spaces. Section 2 is dedicated to our geometric characterization of
the error and the proof of Theorem 1. We also discuss algorithms for numerical
integration and give a first example to illustrate the benefits of our
characterization. In Section 3, we apply the result to random sampling points
for which a limit theorem is derived. Finally, in Section 4, we discuss how
our results may be extended to more general function spaces.

We want to note that there remain several unresolved issues. In particular, we
encourage readers to (a) examine the $d$-dependence of the constants in
Theorem 1, (b) examine and improve upon the computational cost of our
algorithm, (c) derive similar bounds for existing approximation algorithms,
which currently are stated in terms of the covering radius, (d) obtain similar
results for Besov spaces, and (e) study more general domains.

##  1 Preliminaries

Let us first fix some basic notation. For $d\in\mathbb{N}$ and
$0<p\leq\infty$, we write

$\|x\|_{p}:=\begin{cases}\big{(}|x_{1}|^{p}+\cdots+|x_{d}|^{p}\big{)}^{1/p},&\text{if
}0<p<\infty,\\\ \max_{1\leq i\leq d}|x_{i}|,&\text{if }p=\infty\end{cases}$

for the $\ell^{p}$-(quasi-)norm of $x=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}$.
The space $\mathbb{R}^{d}$ will be equipped with the standard inner product
$\langle\cdot,\cdot\rangle$. We write
$B_{d}^{p}(x,r):=\\{y\in\mathbb{R}^{d}:\|x-y\|_{p}<r\\}$ for the
$\ell^{p}$-ball of radius $r>0$ centered at $x$. If $c>0$, we write
$cB_{d}^{p}(x,r)$ for the concentric $\ell^{p}$-ball $B_{d}^{p}(x,cr)$. If
$p=2$, we often omit the $p$ in these notations. We write $\mathbb{S}^{d-1}$
for the unit sphere, which is the boundary of $B_{d}^{2}(0,1)$. We denote the
$d$-dimensional Lebesgue-measure by $\operatorname{vol}_{d}$ and frequently
omit the dimension $d$.

We assume that all random variables are defined on a common probability space
$(S,\Sigma,\mathbb{P})$. For a set $\Omega\subset\mathbb{R}^{d}$ with finite
and positive volume, an $\mathbb{R}^{d}$-valued random variable $X$ will be
called a uniformly distributed point in $\Omega$ if $\mathbb{P}\,[X\in
A]=\operatorname{vol}(A\cap\Omega)/\operatorname{vol}(\Omega)$ for all
Lebesgue-measurable $A\subset\mathbb{R}^{d}$.

The space of all continuous functions $f\colon\Omega\to\mathbb{R}$ on an open
set $\Omega\subset\mathbb{R}^{d}$ is denoted by $C(\Omega)$. We write $f|_{B}$
for the restriction of $f\colon A\to\mathbb{R}$ to $B\subset
A\subset\mathbb{R}^{d}$. The space of polynomials on $\mathbb{R}^{d}$ of
degree at most $m\in\mathbb{N}$ is written $\mathcal{P}_{m}^{d}$. If
$0<p<\infty$, the function space $L_{p}(\Omega)$ is the collection of all
(equivalence classes of) Lebesgue-measurable functions
$f\colon\Omega\to\mathbb{R}$ with finite (quasi-)norm
$\|f\|_{L_{p}(\Omega)}:=\big{(}\int_{\Omega}|f(x)|^{p}{\rm d}x\big{)}^{1/p}$.
The space $L_{\infty}(\Omega)$ is the space of all essentially bounded
functions $f\colon\Omega\to\mathbb{R}$ equipped with the norm
$\|f\|_{L_{\infty}(\Omega)}:={\rm{esssup}}_{x\in\Omega}|f(x)|$. We use the
convention that $a/0=\infty$ and $a/\infty=0$ as well as $\infty/a=\infty$ for
all $a\in(0,\infty)$.

For two nonnegative functions $a$ and $b$ defined on the same set, we will
write $a\preccurlyeq b$ whenever $a\leq cb$ holds for a third function $c$
that only depends on a specific list of parameters. Unless specified
otherwise, this list consists of the domain $\Omega$, the dimension
$d\in\mathbb{N}$, the smoothness parameter $s>0$, and the integrability
parameters $p,\tau,q,\gamma,\gamma_{1},\gamma_{2}\,{>0}$. The function $c$ is
called the implied constant. We write $a\succcurlyeq b$ if $b\preccurlyeq a$
holds and $a\asymp b$ if both relations are satisfied.

###  1.1 Domains and discrete sets

In the following, let $\Omega\subset\mathbb{R}^{d}$ be a bounded domain (i.e.,
open and nonempty) and let $P\subset\mathbb{R}^{d}$ be finite and nonempty. We
are interested in the $L_{\gamma}(\Omega)$-norm of the distance function

$\operatorname{dist}(\cdot,P)\colon\mathbb{R}^{d}\to[0,\infty),\qquad\operatorname{dist}(x,P):=\min_{y\in
P}\|x-y\|_{2}$

for $0<\gamma\leq\infty$. In particular, for $\gamma=\infty$, we obtain the
covering radius

$h_{P,\Omega}:=\sup_{x\in\Omega}\operatorname{dist}(x,P)=\|\operatorname{dist}(\cdot,P)\|_{L_{\infty}(\Omega)}$

of $P$ with respect to $\Omega$. This is the minimal radius such that the
(closures of the) balls $B(x,h_{P,\Omega}),$ where $x\in P,$ cover $\Omega$.
Clearly, the finite volume of $\Omega$ gives
$\|\operatorname{dist}(\cdot,P)\|_{L_{\gamma_{1}}(\Omega)}\preccurlyeq\|\operatorname{dist}(\cdot,P)\|_{L_{\gamma_{2}}(\Omega)}$,
whenever $0<\gamma_{1}\leq\gamma_{2}\leq\infty$. Moreover, it is well known
that we have

$\inf_{|P|\leq
n}\|\operatorname{dist}(\cdot,P)\|_{L_{\gamma}(\Omega)}\,\asymp\,n^{-1/d}\qquad\text{for
every}\quad 0<\gamma\leq\infty.$ (4)

The upper bound is quite obvious since the bounded set $\Omega$ may be covered
by $n$ balls of radius $\asymp n^{-1/d}$. The lower bound is due to a standard
volume argument: We choose the constant $c$ such that the union of the $n$
balls with center in $P$ and radius $cn^{-1/d}$ has volume at most
$\operatorname{vol}(\Omega)/2$, which means that
$\operatorname{dist}(\cdot,P)\geq cn^{-1/d}$ on a subset of $\Omega$ with
volume at least $\operatorname{vol}(\Omega)/2$.

A special Lipschitz domain in $\mathbb{R}^{d}$, $d\geq 2$, is the collection
of all points $x=(x^{\prime},x_{d})$ with $x^{\prime}\in\mathbb{R}^{d-1}$ such
that

$h(x^{\prime})<x_{d}<\infty,$

where $h\colon\mathbb{R}^{d-1}\to\mathbb{R}$ is some Lipschitz function, i.e.,
there exists a constant $C>0$ with $|h(x^{\prime})-h(y^{\prime})|\leq
C\|x^{\prime}-y^{\prime}\|_{2}$ for all
$x^{\prime},y^{\prime}\in\mathbb{R}^{d-1}$. The set $\Omega$ is called a
bounded Lipschitz domain (cf. [22]) if there are points
$x_{1},\ldots,x_{N}\in\partial\Omega$ on the boundary and radii
$r_{1},\ldots,r_{N}>0$ such that $\partial\Omega$ is covered by the balls
$B(x_{1},r_{1}),\ldots,B(x_{N},r_{N})$ and

$B(x_{i},r_{i})\cap\Omega=B(x_{i},r_{i})\cap\Omega_{i},\quad i=1,\ldots,N,$

where $\Omega_{i}$ is a suitable rotation of a special Lipschitz domain in
$\mathbb{R}^{d}$.

A (closed) cone with apex $x\in\mathbb{R}^{d}$, direction
$\xi\in\mathbb{S}^{d-1}$, height (or radius) $r>0$ and opening angle
$\theta\in(0,\pi/2)$ is given by

$C(x,\xi,r,\theta):=\left\\{x+\lambda y\colon y\in\mathbb{S}^{d-1},\langle
y,\xi\rangle\geq\cos\theta,\lambda\in[0,r]\right\\}.$

We will need Lemma 3.7 from [35] in the following special case.

######  Lemma 1.

Every cone $C(x,\xi,r,\theta)$ contains a ball of radius $c_{\theta}r$ with
$c_{\theta}:=\frac{\sin\theta}{1+\sin\theta}$.

A general set $\Omega\subset\mathbb{R}^{d}$ is said to satisfy an interior
cone condition (cf. [35]) if there are $r>0$ and $\theta\in(0,\pi/2)$ such
that for all $x\in\Omega$ there is a unit vector $\xi(x)\in\mathbb{S}^{d-1}$
such that the cone $C(x,\xi(x),r,\theta)$ is contained in $\Omega$. The
following simple observations will be useful.

######  Lemma 2.

Let $\Omega\subset\mathbb{R}^{d}$ satisfy an interior cone condition with
parameters $r$ and $\theta$. If $B(x,\varrho)$ is a ball with center
$x\in\Omega$ and radius $0<\varrho\leq r$, there is a ball
$B(y,c_{\theta}\varrho)$ contained in $B(x,\varrho)\cap\Omega$ with
$c_{\theta}$ as in Lemma 1.

###### Proof.

By the cone condition, there is a cone with apex $x$, height $\varrho$ and
angle $\theta$ such that its interior is contained in
$B(x,\varrho)\cap\Omega$. Now Lemma 1 completes the proof. ∎

Convex domains satisfy an interior cone condition, see e.g. [35, Proposition
11.26].

######  Lemma 3.

Let $\Omega\subset\mathbb{R}^{d}$ be a bounded convex domain containing a ball
of radius $r$. Then the closure of $\Omega$, denoted $\overline{\Omega}$,
satisfies an interior cone condition with radius $r$ and angle
$\theta=2\arcsin\bigl{(}r/2\operatorname{diam}(\Omega)\bigr{)}$.

Convex domains are also Lipschitz domains. A similar result may be found in
Dekel and Leviatan [7, Lemma 2.3].

######  Lemma 4.

Every bounded convex domain is a bounded Lipschitz domain.

###### Proof.

If $\Omega\subset\mathbb{R}^{d}$ is a bounded convex domain, we find a ball
$B(x_{0},r)\subset\Omega$. As $\partial\Omega$ is compact, there are points
$x_{1},\ldots,x_{N}$ such that the balls $B(x_{i},r/2)$, $i\leq N$, cover
$\partial\Omega$. For all $i\leq N$ we show that

$B(x_{i},r/2)\cap\Omega=B(x_{i},r/2)\cap\Omega_{i},$ (5)

where $\Omega_{i}$ is a rotation of a special Lipschitz domain in
$\mathbb{R}^{d}$. Applying a suitable rotation (and translation), we may
assume that $x_{0}=0$ and that $x_{i}=(0,\ldots,0,a)$ for some $a\leq-r$.
Consider the open ball $B^{\prime}=B_{d-1}(0,r)$ in $\mathbb{R}^{d-1}$. For
$x^{\prime}\in B^{\prime}$, we define the set
$A(x^{\prime})=\\{x_{d}\in\mathbb{R}\colon(x^{\prime},x_{d})\in\Omega\\}$.
Since $\Omega$ is convex and open, $A(x^{\prime})$ is an open interval.
Moreover, $A(x^{\prime})$ is nonempty since $0\in A(x^{\prime})$. We define
$h(x^{\prime})$ to be the infimum of $A(x^{\prime})$. The convexity of
$\Omega$ implies that the function $h\colon B^{\prime}\to\mathbb{R}$ is
convex. Since every convex function on a convex domain in $\mathbb{R}^{d-1}$
is Lipschitz on every compact subset of the domain, see [34], the function $h$
is Lipschitz on the closure of the ball $B^{*}=B_{d-1}(0,r/2)$. This Lipschitz
continuity carries over to the whole $\mathbb{R}^{d-1}$ if we set $h(\lambda
x^{\prime})=h(x^{\prime})$ for all $x^{\prime}\in\partial B^{*}$ and
$\lambda\geq 1$ (thereby redefining $h$ on $B^{\prime}\setminus B^{*}$). It
remains to note that for every $x=(x^{\prime},x_{d})\in B(x_{i},r/2)$ it holds
that

$x\in\Omega\quad\Leftrightarrow\quad x_{d}\in
A(x^{\prime})\quad\Leftrightarrow\quad x_{d}>h(x^{\prime}),$

proving (5) for the special Lipschitz domain
$\Omega_{i}=\\{(x^{\prime},x_{d})\colon x_{d}>h(x^{\prime})\\}$. ∎

It seems to be well known that bounded Lipschitz domains satisfy an interior
cone condition. This is used in [22] and also stated by Adams and Fournier [1,
4.11] for domains with the strong local Lipschitz condition, which include
bounded Lipschitz domains. Since we did not find it elsewhere, we include the
proof.

######  Lemma 5.

Every bounded Lipschitz domain satisfies an interior cone condition.

###### Proof.

We first show that special Lipschitz domains satisfy an interior cone
condition. Let therefore

$\Omega_{0}=\left\\{x=(x^{\prime},x_{d})\in\mathbb{R}^{d}\colon
x_{d}>h(x^{\prime})\right\\}$

where $h\colon\mathbb{R}^{d-1}\to\mathbb{R}$ is a Lipschitz continuous
function and $d\geq 2$. We set

$L=\sup_{x\neq y}\frac{|h(x)-h(y)|}{\|x-y\|},\qquad\theta=\arctan
L^{-1},\qquad\xi=(0,\ldots,0,1)\in\mathbb{R}^{d}$

and $\theta=\pi/2$ if $L=0$. Let $x=(x^{\prime},x_{d})\in\Omega_{0}$ and
$z=(z^{\prime},z_{d})\in C(x,\xi,\infty,\theta)$. Then we have $z=x+\lambda y$
for some $\lambda\geq 0$ and $y\in\mathbb{S}^{d-1}$ with
$y_{d}\geq\cos\theta$, and therefore,

$z_{d}=x_{d}+\lambda y_{d}>h(x^{\prime})+\lambda\cos\theta\geq
h(z^{\prime})-L\|z^{\prime}-x^{\prime}\|+\lambda\cos\theta\\\
=h(z^{\prime})-L\lambda\sqrt{1-y_{d}^{2}}+\lambda\cos\theta\geq
h(z^{\prime})+\lambda(\cos\theta-L\sin\theta)=h(z^{\prime}).$

We thus obtain that $C(x,\xi,\infty,\theta)\subset\Omega_{0}$ for all
$x\in\Omega_{0}$.

Let now $\Omega\subset\mathbb{R}^{d}$ be a bounded Lipschitz domain. Choose
points $x_{1},\ldots,x_{N}\in\partial\Omega$ and radii $r_{1},\ldots,r_{N}>0$
such that $\partial\Omega$ is covered by the balls $B_{i}=B(x_{i},r_{i})$ and
$B_{i}\cap\Omega=B_{i}\cap\Omega_{i}$, where $i\leq N$ and $\Omega_{i}$ is a
rotation of a special Lipschitz domain. Clearly, the interior cone condition
is preserved under rotations, such that the $\Omega_{i}$ satisfy an interior
cone condition with angle $\theta_{i}$ (and infinite height). First, we note
that there is some $a\in(0,1)$ such that the balls $aB_{i}$ still cover
$\partial\Omega$: Else, using the compactness of $\partial\Omega$, we would
obtain a convergent sequence $(y_{k})$ in $\partial\Omega$ with
$\|y_{k}-x_{i}\|\geq(1-1/k)r_{i}$ for all $k\in\mathbb{N}$ and $i\leq N$. Its
limit $y\in\partial\Omega$ would satisfy $\|y-x_{i}\|\geq r_{i}$ and therefore
$y\not\in B_{i}$, a contradiction.

Let thus $b=(a+1)/2$, $r=\min_{i}r_{i}$ and $\theta=\min_{i}\theta_{i}$, and
let $x\in\Omega$. If $x\in bB_{i}$ for some $i\leq N$, then there is a cone
with apex $x$, height $(1-b)r=(1-a)r/2$ and angle $\theta$ which is contained
in both $B_{i}$ and $\Omega_{i}$ and therefore in $\Omega$. On the other hand,
if $x\not\in bB_{i}$ for all $i\leq N$, then the whole ball with center $x$
and radius $(b-a)r=(1-a)r/2$ is contained in $\Omega$: Else, there would be
some $y\in\partial\Omega$ with $\|y-x\|\leq(b-a)r$ and since $y\in aB_{i}$ for
some $i\leq N$ also $\|x_{i}-x\|<ar_{i}+(b-a)r\leq br_{i}$, which is a
contradiction. Thus $\Omega$ satisfies an interior cone condition with angle
$\theta$ and height $(1-a)r/2$. ∎

A convex domain also satisfies the following local version of the cone
condition.

######  Lemma 6.

Let $\Omega\subset\mathbb{R}^{d}$ be a bounded convex domain containing a ball
of radius $r>0$. Then the closure of the intersection of $\Omega$ with any
cube $B_{d}^{\infty}(x,\varrho)$ centered at $x\in\overline{\Omega}$ and
having $\ell^{\infty}$-radius $0<\varrho\leq r$ satisfies an interior cone
condition with height $c_{\theta}\varrho$ and angle
$\theta^{\prime}=2\arcsin(c_{\theta}/4\sqrt{d})$, where $c_{\theta}$ is as in
Lemma 1 and $\theta$ is as in Lemma 3.

###### Proof.

By Lemma 3, the set $\overline{\Omega}$ contains a cone with height
$\varrho\leq r$, apex $x$ and angle $\theta$. Clearly, this cone is contained
in $\overline{\Omega\cap B(x,\varrho)}$, which is a subset of
$A(x,\varrho):=\overline{\Omega\cap B_{d}^{\infty}(x,\varrho)}$. By Lemma 1,
there is a ball $B(y,c_{\theta}\varrho)$ in this cone and thus in
$A(x,\varrho)$. The proof is finished if we apply Lemma 3 to the convex set
$A(x,\varrho)$ since its diameter is at most $2\varrho\sqrt{d}$. ∎

One of our main tools will be the following result due to Wendland, which we
state (almost) in the formulation of Theorem 4.7 in his book [35]. It will
provide us with a well-behaved linear algorithm.

######  Lemma 7 ([35]).

Let $K\subset\mathbb{R}^{d}$ be a compact set satisfying an interior cone
condition with parameters $r$ and $\theta$, and let $m\in\mathbb{N}$. There
are constants $c_{0},c_{1},c_{2}>0$ depending solely on $\theta,m$ and $d$
such that for any finite nonempty $P\subset K$ with covering radius
$h_{P,K}\leq c_{1}r$ there exist continuous functions $u_{x}\colon
K\to\mathbb{R}$, $x\in P,$ with

  1. _(i)_

$\displaystyle\pi(y)=\sum_{x\in P}\pi(x)u_{x}(y)$ for all $y\in K$ and
$\pi\in\mathcal{P}_{m}^{d}$,

  2. _(ii)_

$\displaystyle\sum_{x\in P}|u_{x}(y)|\leq c_{0}$ for all $y\in K$ and

  3. _(iii)_

$u_{x}(y)=0$ for all $y\in K$ and $x\in P$ with $\|x-y\|\geq c_{2}h_{P,K}$.

###### Proof.

To derive this statement from [35, Theorem 4.7], we will show that there is a
subset $X$ of $P$ with $h_{X,K}\leq 2h_{P,K}$ and separation distance

$q_{X}:=\frac{1}{2}\min_{x,y\in X,x\neq y}\|x-y\|_{2}\geq\frac{1}{2}h_{P,K}$

and apply Theorem 4.7 to the subset $X$ (setting $u_{x}=0$ for all $x\in
P\setminus X$). To this end, we choose an arbitrary $x_{1}\in P$ and
recursively choose $x_{i}\in P\setminus\bigcup_{j<i}B(x_{j},h_{P,K})$ until
the latter set is empty. We obtain a subset $X$ of $P$ which clearly satisfies
$q_{X}\geq\frac{1}{2}h_{P,K}$. Moreover, for any $y\in K$, there is some $x\in
P$ with $\|y-x\|_{2}\leq h_{P,K}$. Since $P\setminus\bigcup_{\tilde{x}\in
X}B(\tilde{x},h_{P,K})=\emptyset$, there is some $\tilde{x}\in X$ with
$\|x-\tilde{x}\|_{2}\leq h_{P,K}$. The triangle inequality gives
$\|y-\tilde{x}\|_{2}\leq 2h_{P,K}$ and therefore $h_{X,K}\leq 2h_{P,K}$. ∎

###  1.2 Sobolev spaces

Let $\Omega\subset\mathbb{R}^{d}$ be a domain. For $s\in\mathbb{N}$ and $1\leq
p\leq\infty$ we consider the Sobolev space

$W^{s}_{p}(\Omega):=\big{\\{}f\in
L_{p}(\Omega)\colon\|f\|_{W^{s}_{p}(\Omega)}:=\Big{(}\sum_{|\alpha|\leq
s}\|D^{\alpha}f\|_{L_{p}(\Omega)}^{p}\Big{)}^{1/p}<\infty\big{\\}},$

where $\alpha\in\mathbb{N}_{0}^{d}$ is a multiindex,
$|\alpha|=\alpha_{1}+\ldots+\alpha_{d}$ and
$D^{\alpha}f=\frac{\partial^{|\alpha|}}{\partial
x_{1}^{\alpha_{1}}\cdots\partial x_{d}^{\alpha_{d}}}f$ denotes a weak partial
derivative of order $|\alpha|$. This is a Banach space with respect to the
norm $\|\cdot\|_{W^{s}_{p}(\Omega)}$. In addition to the norm, we will also
work with the semi-norm

$|f|_{W^{s}_{p}(\Omega)}:=\Big{(}\sum_{|\alpha|=s}\|D^{\alpha}f\|_{L_{p}(\Omega)}^{p}\Big{)}^{1/p},$

which has better scaling properties. If $\Omega$ is sufficiently regular,
functions from the Sobolev space $W^{s}_{p}(\Omega)$ may be extended to
$W^{s}_{p}(\mathbb{R}^{d})$, see Stein [29, Section VI.3]. Note that Stein
uses the notion of minimally smooth domains which entails bounded Lipschitz
domains.

######  Lemma 8 ([29]).

Let $\Omega\subset\mathbb{R}^{d}$ be a bounded Lipschitz domain, $1\leq
p\leq\infty$ and $s\in\mathbb{N}$ with $s>d/p$. Then there is a bounded linear
operator ${\rm ext}\colon W^{s}_{p}(\Omega)\to W^{s}_{p}(\mathbb{R}^{d})$ with
${\rm ext}(f)|_{\Omega}=f$ for all $f\in W^{s}_{p}(\Omega)$.

We will also use the following result about optimal polynomial approximation
on $\ell^{\infty}$-balls, which follows e.g. from Maz’ya [19, Lemma 1.1.11].

######  Lemma 9 ([19]).

For any $1\leq p\leq\infty$ and $s\in\mathbb{N}$ with $s>d/p$, there is a
constant $c_{\ast}>0$ such that the following holds. For any $0<\varrho\leq
1$, any $\ell^{\infty}$-ball $Q$ of radius $\varrho$ and any $f\in
W^{s}_{p}(Q)$, there is a polynomial $\pi$ of degree at most $s$ such that

$\sup_{x\in Q}|(f-\pi)(x)|\leq c_{\ast}\,\varrho^{s-d/p}|f|_{W_{p}^{s}(Q)}.$

###### Proof.

We simply use Maz’ya’s result for $f\circ T^{-1}$ on the domain $(0,1)^{d}$,
where $T$ is an affine mapping with $TQ=(0,1)^{d}$ and rescale. Together with
the continuous embedding $W^{s}_{p}\bigl{(}(0,1)^{d}\bigr{)}\hookrightarrow
C\bigl{(}(0,1)^{d}\bigr{)}$ the proof is complete. ∎

##  2 The geometric characterization

In this section, we give a proof of our main result, Theorem 1. For the proof,
let us fix $\Omega$ and $p,q,s$ as in the statement of Theorem 1. All
constants in this section are allowed to depend on these parameters. Let
$r\leq 1$ and $\theta\in(0,\pi/2)$ be such that $\Omega$ contains a ball of
radius $r$ and $\overline{\Omega}$ satisfies an interior cone condition with
radius $r$ and angle $\theta$, see Lemma 3. In Section 2.1, we first prove the
characterization in the simpler case $q\geq p$, where only the largest hole
amidst the point set matters. In this case, an optimal algorithm of the form
(1) is given by Wendland’s polynomial reproducing map on $\Omega$, see Lemma 7
and also [21]. The case $q<p$ is more involved and will be treated in Section
2.2. There, we will also apply Wendland’s result, but locally. We then turn to
numerical integration in Section 2.3 and conclude this chapter with an example
in Section 2.4.

###  2.1 The case $q\geq p$

Let us start with the upper bound. We basically extend the proof of [22,
Proposition 21] to point sets with non-optimal covering radius. To this end,
let $m>s$ be an integer and let $c_{0},c_{1},c_{2}>0$ be as in Lemma 7. We can
assume that $h_{P,\Omega}\leq c_{1}r$ as the upper bound is trivial if this
does not hold. We consider the linear algorithm

$S_{P}\colon W_{p}^{s}(\Omega)\to L_{q}(\Omega),\quad S_{P}(f)=\sum_{x\in
P}f(x)u_{x},$

with $u_{x}$ provided by Lemma 7 for the compact set $\overline{\Omega}$. The
balls $B(y,h_{P,\Omega})$, $y\in\Omega$, cover the set $\overline{\Omega}$. By
compactness and Vitali’s Lemma, there is a finite selection of pairwise
disjoint balls $B_{i}=B(y_{i},h_{P,\Omega})$ with $y_{i}\in\Omega$ and $i\leq
N$ such that the balls $3B_{i}=B(y_{i},3h_{P,\Omega})$ still cover
$\overline{\Omega}$.

Let $f\in W_{p}^{s}(\Omega)$ with $\|f\|_{W_{p}^{s}(\Omega)}\leq 1$. By Lemma
8, we may assume that $f\in W_{p}^{s}(\mathbb{R}^{d})$ with
$\|f\|_{W_{p}^{s}(\mathbb{R}^{d})}\leq c_{3}$. Let $Q_{i}$ be the cube around
$y_{i}$ with radius $(3+c_{2})h_{P,\Omega}$. By Lemma 9, there are polynomials
$\pi_{i}$ of degree at most $s$ such that

$\sup_{y\in Q_{i}}\big{|}(f-\pi_{i})(y)\big{|}\leq
c_{4}\,h_{P,\Omega}^{s-d/p}|f|_{W_{p}^{s}(Q_{i})}.$

For each $y\in\Omega_{i}:=3B_{i}\cap\Omega$, we note that $u_{x}(y)=0$ for
$x\not\in Q_{i}$, and obtain

$\displaystyle\big{|}(f-S_{P}f)(y)\big{|}$
$\displaystyle=\big{|}(f-\pi_{i})(y)-S_{P}(f-\pi_{i})(y)\big{|}$
$\displaystyle\leq\big{|}(f-\pi_{i})(y)\big{|}+\Big{|}\sum_{x\in
P}(f-\pi_{i})(x)u_{x}(y)\Big{|}\leq
c_{5}\,h_{P,\Omega}^{s-d/p}|f|_{W_{p}^{s}(Q_{i})},$ (6)

where $c_{5}=(1+c_{0})c_{4}$. In particular, this yields

$\|f-S_{P}(f)\|_{L_{\infty}(\Omega)}\leq
c_{5}\,h_{P,\Omega}^{s-d/p}|f|_{W_{p}^{s}(\mathbb{R}^{d})},$

which proves the case $q=\infty$. For $p\leq q<\infty$, we use
$\Omega_{i}\subset Q_{i}$ and (6) to get

$\|f-S_{P}(f)\|_{L_{q}(\Omega)}^{q}\leq\sum_{i=1}^{N}\int_{\Omega_{i}}\big{|}\big{(}f-S_{P}(f)\big{)}(y)\big{|}^{q}{\rm
d}y\leq c_{5}^{q}\sum_{i=1}^{N}\,h_{P,\Omega}^{sq-
dq/p}|f|_{W_{p}^{s}(Q_{i})}^{q}\operatorname{vol}(\Omega_{i})\\\ \leq
c_{6}\,h_{P,\Omega}^{sq-dq/p+d}\sum_{i=1}^{N}|f|_{W_{p}^{s}(Q_{i})}^{q}\leq
c_{6}\,h_{P,\Omega}^{sq-
dq/p+d}\Big{(}\sum_{i=1}^{N}|f|_{W_{p}^{s}(Q_{i})}^{p}\Big{)}^{q/p}.$

Note that, independently of $P$, every $x\in\mathbb{R}^{d}$ is contained in at
most $c_{7}\in\mathbb{N}$ of the $N$ cubes $Q_{i}$ since the balls $B_{i}$ are
disjoint and all have the same radius. Therefore,

$\sum_{i=1}^{N}|f|_{W_{p}^{s}(Q_{i})}^{p}=\sum_{|\alpha|=s}\int_{\mathbb{R}^{d}}\Big{(}|D^{\alpha}f(x)|^{p}\sum_{i=1}^{N}\mathbbm{1}_{Q_{i}}(x)\Big{)}{\rm
d}x\leq c_{7}\,|f|_{W_{p}^{s}(\mathbb{R}^{d})}^{p}\leq c_{7}c_{3}^{p}$ (7)

and we arrive at the desired inequality.

For the lower bound we use the well-known technique of _fooling functions_ :
We construct a function $f_{\ast}$ from the unit ball of $W_{p}^{s}(\Omega)$
which vanishes on $P$ and has a large $L_{q}$-norm. Since any algorithm of the
form (1) cannot distinguish $f_{\ast}$ from $-f_{\ast}$, i.e., it satisfies
$S_{P}(f_{*})=S_{P}(-f_{*})$, we have

$\begin{split}e\big{(}P,W_{p}^{s}(\Omega)&\hookrightarrow
L_{q}(\Omega)\big{)}\,=\,\inf_{S_{P}}\sup_{\|f\|_{W^{s}_{p}(\Omega)}\leq
1}\|S_{P}(f)-f\|_{L_{q}(\Omega)}\\\ &\geq\,\inf_{u\in
L_{q}(\Omega)}\,\max\left\\{\|u-f_{*}\|_{L_{q}(\Omega)},\|u+f_{*}\|_{L_{q}(\Omega)}\right\\}\geq\,\|f_{\ast}\|_{L_{q}(\Omega)}.\end{split}$
(8)

In the case $q\geq p$ it is enough to consider a function $f_{\ast}$ which is
supported in the largest hole, compare [16, Theorem 11] for
$\Omega=[0,1]^{d}$. Let therefore $x_{0}\in\Omega$ be such that
$\operatorname{dist}(x_{0},P)\geq h:=\min\\{r,\frac{1}{2}h_{P,\Omega}\\}$.
Then the ball $B(x_{0},h)$ does not contain any point of $P$. By Lemma 2 we
find a ball $B(y,\varrho)$ with $\varrho:=c_{\theta}h,$ which is contained in
$\Omega\cap B(x_{0},h)$. We take a smooth non-negative function $\varphi$
supported in $B(0,1)$ with $\varphi(0)=1$ and consider
$f(x)=\varphi\big{(}\varrho^{-1}(x-y)\big{)}$. One can easily compute the
scaling properties

$\|f\|_{L_{q}(\Omega)}\asymp\varrho^{d/q}\qquad\text{and}\qquad\|f\|_{W^{s}_{p}(\Omega)}\preccurlyeq\varrho^{-s+d/p},$
(9)

taking into account that $\varrho\leq 1$ and $s>d/p$. This yields that
$f_{*}:=\|f\|_{W^{s}_{p}(\Omega)}^{-1}f$ satisfies

$\|f_{*}\|_{W^{s}_{p}(\Omega)}\leq 1,\quad
f_{*}|_{P}=0\quad\text{and}\quad\|f_{*}\|_{L_{q}(\Omega)}\succcurlyeq
h_{P,\Omega}^{s-d(1/p-1/q)},$

which completes the proof. $\hfill\square$

###  2.2 The case $q<p$

We start with the upper bound, using the following approximation property. As
this useful result is somewhat technical, let us paraphrase it with “Locally
good point sets yield locally good approximations”.

######  Lemma 10.

Let $\Omega$, $p$ and $s$ as in Theorem 1. There are constants $c\in(0,1)$ and
$C>0$, depending solely on $d,\theta,s$ and $p$, such that for any cube
$Q=B_{d}^{\infty}(x,\varrho)\subset\mathbb{R}^{d}$ of radius $0<\varrho\leq r$
centered at $x\in\overline{\Omega}$ and any finite point set $P\subset\Omega$
with

$\sup_{y\in\Omega\cap Q}\operatorname{dist}(y,P)\leq c\varrho,$ (10)

there are continuous functions $u_{x}\colon\Omega\cap Q\to\mathbb{R}$, $x\in
P$, such that for any $f\in W^{s}_{p}(\mathbb{R}^{d})$, we have

$\sup_{y\in\Omega\cap Q}\Big{|}f(y)-\sum_{x\in P}f(x)u_{x}(y)\Big{|}\leq
C\varrho^{s-d/p}|f|_{W^{s}_{p}(Q)}.$

###### Proof.

By Lemma 6 the set $\overline{\Omega\cap Q}$ satisfies an interior cone
condition with radius $\varrho^{\prime}=c_{\theta}\varrho$ and angle
$\theta^{\prime}$. Let $m\in\mathbb{N}$ be the smallest integer greater than
$s$ and let $c_{0},c_{1}>0$ be as in Lemma 7 for the parameters
$\theta^{\prime}$ and $m$. Note that $c_{1}$ can be chosen to be smaller than
one. We set $c=c_{\theta}c_{\theta^{\prime}}c_{1}/2$ with
$c_{\theta^{\prime}}$ as in Lemma 1. Then assumption (10) implies that every
ball $B(y,2c\varrho)$, $y\in Q\cap\Omega$, contains a point of $P$. By Lemma 2
every ball $B(x,2c_{\theta^{\prime}}^{-1}c\varrho),x\in Q\cap\Omega,$ contains
a ball $B(y,2c\varrho)\subset Q\cap\Omega$ and therefore a point of $P\cap Q$.
We thus have

$h_{P\cap Q,\Omega\cap Q}\leq
2c_{\theta^{\prime}}^{-1}c\varrho=c_{1}\varrho^{\prime}.$

Thus, we may apply Lemma 7 to the point set $P\cap Q$ within the compact set
$\overline{\Omega\cap Q}$ and obtain continuous functions
$u_{x}\colon\Omega\cap Q\to\mathbb{R}$ for $x\in P$ with

$\sum_{x\in P}|u_{x}(y)|\leq c_{0}\qquad\text{and}\qquad\pi(y)=\sum_{x\in
P}\pi(x)u_{x}(y)$

for all $\pi\in\mathcal{P}_{m}^{d}$ and $y\in\Omega\cap Q$, where we set
$u_{x}=0$ for $x\in P\setminus Q$. For any $f\in W^{s}_{p}(\mathbb{R}^{d})$,
by Lemma 9 there is a polynomial $\pi\in\mathcal{P}_{m}^{d}$ with

$\sup_{y\in
Q}\big{|}(f-\pi)(y)\big{|}\,\leq\,c_{\ast}\varrho^{s-d/p}|f|_{W^{s}_{p}(Q)}.$

Similar to Section 2.1, we get for all $y\in\Omega\cap Q$ that

$\Big{|}f(y)-\sum_{x\in P}f(x)u_{x}(y)\Big{|}=\Big{|}(f-\pi)(y)-\sum_{x\in
P}(f-\pi)(x)u_{x}(y)\Big{|}\\\
\,\leq\,\big{|}(f-\pi)(y)\big{|}+c_{0}\,\max_{x\in P\cap
Q}\big{|}(f-\pi)(x)\big{|}\,\leq\,(1+c_{0})c_{\ast}\,\varrho^{s-d/p}|f|_{W^{s}_{p}(Q)},$

as it was to be proven. ∎

In the following, we say that a cube $Q$ is a _good cube_ if it satisfies the
conditions of Lemma 10. We now define good cubes $Q_{P}(x)$ for all
$x\in\overline{\Omega}$. Without loss of generality, we may assume that for
any $x\in\overline{\Omega}$ there is some $\varrho\in(0,r)$ such that

$\sup_{y\in\Omega\cap
B_{d}^{\infty}(x,\varrho)}\operatorname{dist}(y,P)<c\varrho,$ (11)

where $c$ is the constant from Lemma 10. Otherwise,
$\operatorname{dist}(\cdot,P)$ is larger than a constant on a set of constant
volume and the upper bound of Theorem 1a becomes trivial. We define $r_{P}(x)$
to be the infimum over all $\varrho\in(0,r)$ satisfying (11) and let
$Q_{P}(x):=B_{d}^{\infty}\big{(}x,r_{P}(x)\big{)}$. Our definition ensures
that $Q_{P}(x)$ is indeed a good cube. We will now show that there is a
covering of the domain by such cubes that is efficient in the sense that every
point is covered only by a constant number of cubes. For this, we need the
following observation.

######  Lemma 11.

The function $r_{P}\colon\overline{\Omega}\to(0,\infty)$ is upper semi-
continuous.

###### Proof.

Let $x\in\overline{\Omega}$. We first show $r_{P}(x)>0$. If $\varrho>0$ is
small enough, then $B_{d}^{\infty}(x,\varrho)$ does not contain any point of
$P$ except possibly $x$. Since $c<1$, relation (11) cannot be satisfied for
these values of $\varrho$ and thus $r_{P}(x)$ is positive. To show the semi-
continuity, let $\varepsilon>0$. Then there is some
$\varrho\in[r_{P}(x),r_{P}(x)+\varepsilon]$ such that (11) is satisfied.
Clearly, we can choose $\delta>0$ such that (11) is still satisfied if we
replace the right hand side by $ca$ with $a=\varrho-\delta$. For any
$\tilde{x}\in\overline{\Omega}$ with $\|\tilde{x}-x\|_{\infty}<\delta$, the
cube $B_{d}^{\infty}(\tilde{x},a)$ is contained in
$B_{d}^{\infty}(x,\varrho)$. We thus have

$\sup_{y\in
B_{d}^{\infty}(\tilde{x},a)\cap\Omega}\operatorname{dist}(y,P)\leq\sup_{y\in
B_{d}^{\infty}(x,\varrho)\cap\Omega}\operatorname{dist}(y,P)<ca,$

which implies $r_{P}(\tilde{x})\leq a<r_{P}(x)+\varepsilon$. ∎

The semi-continuity is already enough to obtain the desired covering.

######  Lemma 12.

Let $K\subset\mathbb{R}^{d}$ be compact and let $r\colon K\to(0,\infty)$ be
upper semi-continuous. If $K$ is nonempty, then there are points
$y_{1},\ldots,y_{N}\in K$ such that

  1. _(i)_

The cubes $Q_{i}=B_{d}^{\infty}\big{(}y_{i},r(y_{i})\big{)}$, $1\leq i\leq N$,
cover $K$.

  2. _(ii)_

The cubes $Q_{i}/2$ are pairwise disjoint.

  3. _(iii)_

Every $y\in\mathbb{R}^{d}$ is contained in at most $2^{d}$ of the cubes
$Q_{i}$.

###### Proof.

By compactness of $K$, we can choose $y_{1}$ as a maximizer of $r_{P}$ on $K$.
We set $r_{1}=r(y_{1})$ and
$Q_{1}=B_{d}^{\infty}\bigl{(}y_{1},r(y_{1})\bigr{)}$. Recursively, we can
choose $y_{i}$ as a maximizer of $r_{P}$ on $K\setminus\bigcup_{j<i}Q_{j}$
(which is also compact) and set $r_{i}=r(y_{i})$ and
$Q_{i}=B_{d}^{\infty}(y_{i},r_{i})$, as long as the set difference is
nonempty. We first show that the sets
$Q_{i}^{\prime}=B_{d}^{\infty}(y_{i},r_{i}/2)$ are pairwise disjoint. Assume
that $y\in Q_{i}^{\prime}\cap Q_{j}^{\prime}$ for some $j<i$. Then we have

$\|y_{j}-y_{i}\|_{\infty}\leq\|y_{j}-y\|_{\infty}+\|y-y_{i}\|_{\infty}<r_{j}/2+r_{i}/2\leq
r_{j},$

since the numbers $r_{i}$ are nonincreasing, and thus $y_{i}\in Q_{j}$. A
contradiction.

We now show that our procedure terminates after finitely many steps. Assume
for a contradiction that we obtain a whole sequence
$(y_{i})_{i\in\mathbb{N}}$. Then we must have $r_{i}\to 0$, since otherwise we
would have infinitely many disjoint cubes $Q_{i}^{\prime}$ with volume larger
than a constant. There is a subsequence $(y_{i_{k}})_{k\in\mathbb{N}}$ that
converges to some $y_{0}\in K$. By assumption, $r_{0}=r(y_{0})>0$. Since
$r_{i}\to 0$, there is some $k\in\mathbb{N}$ with $r_{k}<r_{0}$. As $r_{k}$ is
a maximum of $r$ on $K\setminus\bigcup_{\ell<k}Q_{\ell}$, the point $y_{0}$
must be contained in $Q_{\ell}$ for some $\ell<k$. Since $Q_{\ell}$ is open
and $y_{i_{k}}\to y_{0}$, we get that $y_{i_{k}}\in Q_{\ell}$ for all
sufficiently large $k$. But by our construction, we have $y_{i}\not\in
Q_{\ell}$ for all $i>\ell$. A contradiction. Thus, the procedure terminates
and we obtain a finite point set $y_{1},\ldots,y_{N}$, satisfying _(i)_ and
_(ii)_.

To prove the efficiency of the covering, let now $y\in\mathbb{R}^{d}$ with
$y\in Q_{i}\cap Q_{j}$ for some $j<i$. Assume that the signs of $y_{i}-y$ and
$y_{j}-y$ are the same (i.e., $y_{i}$ and $y_{j}$ are in the same orthant with
respect to $y$). Then we have

$\|y_{j}-y_{i}\|_{\infty}=\|(y_{j}-y)-(y_{i}-y)\|_{\infty}\leq\max\left\\{\|y_{j}-y\|_{\infty},\|y_{i}-y\|_{\infty}\right\\}<r_{j}$

and thus $y_{i}\in Q_{j}$, a contradiction. This means that the signs of all
$y_{j}-y$ for which $y\in Q_{j}$ must be different – and there are at most
$2^{d}$ different signs. ∎

Lemma 11 and Lemma 12 immediately yield an efficient covering of
$\overline{\Omega}$ by good cubes. It has the following properties.

######  Proposition 2.

Let $\Omega$, $p$ and $s$ as in Theorem 1. For any finite and nonempty point
set $P\subset\Omega$, there are $y_{1},\ldots,y_{N}\in\overline{\Omega}$ such
that the good cubes $Q_{i}=Q_{P}(y_{i})$ with radii $r_{i}=r_{P}(y_{i})$ for
$1\leq i\leq N$ cover $\overline{\Omega}$ and every $y\in\mathbb{R}^{d}$ is
contained in at most $2^{d}$ of these cubes. Each of the cubes $Q_{i}$
contains a ball $B_{i}$ of radius $d_{i}\asymp r_{i}$ such that these balls
are pairwise disjoint subsets of $\Omega$ and empty of $P$.

###### Proof.

With Lemma 11 and Lemma 12 we immediately get an efficient covering by good
cubes $Q_{i}$ such that the cubes $Q_{i}/2$ are disjoint. By the minimality of
$r_{i}$, the set $Q_{i}/4\cap\Omega$ contains a point $z_{i}$ with
$\operatorname{dist}(z_{i},P)\geq cr_{i}/8$, where $c$ is as in Lemma 10. By
Lemma 2, we obtain a ball $B_{i}$ with radius $c_{\theta}cr_{i}/8$ that is
contained in $\Omega\cap B(z_{i},cr_{i}/8)$ and therefore does not contain a
point of $P$. In particular, the balls $B_{i}$ are contained in $Q_{i}/2$ and
are therefore pairwise disjoint. ∎

We are now ready to complete the proof of the upper bound of Theorem 1a for
$q<p$.

###### Proof.

We choose $y_{i}$, $r_{i}$, $d_{i}$, $Q_{i}$ and $B_{i}$ for $1\leq i\leq N$
as in Proposition 2. Let

$\Omega_{i}=(Q_{i}\cap\Omega)\setminus\bigcup_{j<i}\Omega_{j}$

for all $1\leq i\leq N$. That is, $\Omega$ is the disjoint union of the sets
$\Omega_{i}\subset Q_{i}$. For $x\in P$ and $y\in\Omega_{i}$, we define
$u_{x}(y)$ according to Lemma 10, applied to the cube $Q_{i}$. This yields
bounded functions $u_{x}\colon\Omega\to\mathbb{R}$ and a linear algorithm

$S_{P}\colon W^{s}_{p}(\Omega)\to L_{q}(\Omega),\quad S_{P}(f)=\sum_{x\in
P}f(x)u_{x}.$

Let $f\in W^{s}_{p}(\Omega)$ with $\|f\|_{W^{s}_{p}(\Omega)}\leq 1$. Using
Lemma 8 we may assume that $f\in W^{s}_{p}(\mathbb{R}^{d})$ with
$\|f\|_{W^{s}_{p}(\mathbb{R}^{d})}\leq c_{3}$. By Lemma 10 we have

$\|f-S_{P}(f)\|_{L_{q}(\Omega_{i})}^{q}\leq
c_{4}r_{i}^{(s-d/p)q+d}|f|_{W^{s}_{p}(Q_{i})}^{q},$

where $(s-d/p)q+d=(\gamma+d)(1-q/p)$. With the obvious modification for
$p=\infty$, Hölder’s inequality yields

$\|f-S_{P}(f)\|_{L_{q}(\Omega)}^{q}\preccurlyeq\,\sum_{i=1}^{N}r_{i}^{(\gamma+d)(1-q/p)}|f|_{W^{s}_{p}(Q_{i})}^{q}\,\leq\,\bigg{(}\sum_{i=1}^{N}r_{i}^{\gamma+d}\bigg{)}^{1-q/p}\bigg{(}\sum_{i=1}^{N}|f|_{W^{s}_{p}(Q_{i})}^{p}\bigg{)}^{q/p}.$

Since the cubes $Q_{i}$ form an efficient covering, we can proceed as in (7)
to obtain that the second factor in the previous estimate is bounded by a
constant. Since the balls $B_{i}$ of radius $d_{i}\asymp r_{i}$ are pairwise
disjoint subsets of $\Omega\setminus P$, we get
$\operatorname{dist}(\cdot,P)\geq d_{i}/2$ on $B_{i}/2$ and

$\sum_{i=1}^{N}r_{i}^{\gamma+d}\,\preccurlyeq\,\sum_{i=1}^{N}r_{i}^{\gamma}\operatorname{vol}(B_{i})\,\preccurlyeq\,\sum_{i=1}^{N}\int_{B_{i}/2}\operatorname{dist}(x,P)^{\gamma}\,{\rm
d}y\,\leq\,\int_{\Omega}\operatorname{dist}(x,P)^{\gamma}\,{\rm d}y,$

which completes the proof, noting that $(1-q/p)=qs/\gamma$. ∎

We will now prove the lower bound of Theorem 1a for $q<p$. Again we construct
a fooling function with large $L_{q}$-norm that vanishes on the point set.
However, unlike in the case $q\geq p$, the fooling function has to be
supported in multiple holes.

###### Proof.

Let $\varphi\colon\mathbb{R}^{d}\to\mathbb{R}$ be a smooth non-negative
function supported within $B(0,1)$ with $\varphi(0)=1$. We choose $y_{i}$,
$r_{i}$, $Q_{i}$ and $B_{i}=B(z_{i},d_{i})$ for $1\leq i\leq N$ as in
Proposition 2. For every $i\leq N$ and $x\in\mathbb{R}^{d}$ define

$\varphi_{i}(x):=d_{i}^{s+\gamma/p}\varphi\big{(}d_{i}^{-1}(x-z_{i})\big{)}.$

With this, $\varphi_{i}$ is supported in $B(z_{i},d_{i})$. With a substitution
one can see that

$\|\varphi_{i}\|_{L_{q}(\mathbb{R}^{d})}^{q}=d_{i}^{\gamma+d}\|\varphi\|_{L_{q}(\mathbb{R}^{d})}^{q}$

since $q(s+\gamma/p)=\gamma$. With another substitution we obtain for
$p<\infty$ that

$\|\varphi_{i}\|_{W^{s}_{p}(\mathbb{R}^{d})}^{p}\preccurlyeq
d_{i}^{\gamma+d}\|\varphi\|_{W^{s}_{p}(\mathbb{R}^{d})}^{p}.$ (12)

Let $f:=\sum_{i=1}^{N}\varphi_{i}$. Note that $f|_{P}=0$. Since the
$\varphi_{i}$’s have pairwise disjoint support, we have

$\|f\|_{L_{q}(\Omega)}^{q}=\sum_{i=1}^{N}\|\varphi_{i}\|_{L_{q}(\mathbb{R}^{d})}^{q}=\sum_{i=1}^{N}d_{i}^{\gamma+d}\|\varphi\|_{L_{q}(\mathbb{R}^{d})}^{q}.$
(13)

For the same reason we obtain from (12) that

$\|f\|_{W^{s}_{p}(\Omega)}^{p}\asymp\sum_{i=1}^{N}\|\varphi_{i}\|_{W^{s}_{p}(\mathbb{R}^{d})}^{p}\preccurlyeq\sum_{i=1}^{N}d_{i}^{\gamma+d}\|\varphi\|_{W^{s}_{p}(\mathbb{R}^{d})}^{p}.$
(14)

If $p=\infty$, we replace (14) by

$\|f\|_{W^{s}_{\infty}(\Omega)}\asymp\max_{1\leq i\leq
N}\|\varphi_{i}\|_{W^{s}_{\infty}(\mathbb{R}^{d})}\preccurlyeq\|\varphi\|_{W^{s}_{\infty}(\mathbb{R}^{d})}$

and carry on analogously. The estimates (13) and (14) imply for the normalized
function $f_{*}:=\|f\|_{W^{s}_{p}(\Omega)}^{-1}f$ with
$\|f_{*}\|_{W^{s}_{p}(\Omega)}=1$ that

$\|f_{*}\|_{L_{q}(\Omega)}=\frac{\|f\|_{L_{q}(\Omega)}}{\|f\|_{W^{s}_{p}(\Omega)}}\succcurlyeq\left(\sum_{i=1}^{N}d_{i}^{\gamma+d}\right)^{1/q-1/p}\frac{\|\varphi\|_{L_{q}(\mathbb{R}^{d})}}{\|\varphi\|_{W^{s}_{p}(\mathbb{R}^{d})}}.$

Since the cubes $Q_{i}$ cover $\Omega$ (and all contain a point of $P$), we
get

$\sum_{i=1}^{N}d_{i}^{\gamma+d}\,\succcurlyeq\,\sum_{i=1}^{N}d_{i}^{\gamma}\operatorname{vol}(Q_{i})\,\succcurlyeq\,\sum_{i=1}^{N}\int_{Q_{i}}\operatorname{dist}(y,P)^{\gamma}{\rm
d}y\,\succcurlyeq\,\int_{\Omega}\operatorname{dist}(y,P)^{\gamma}{\rm d}y$
(15)

and thus

$\|f_{*}\|_{L_{q}(\Omega)}\succcurlyeq\left(\int_{\Omega}\operatorname{dist}(x,P)^{\gamma}{\rm
d}x\right)^{s/\gamma},$ (16)

where the implied constant also depends on the choice of $\varphi$. As any
algorithm of the form (1) cannot distinguish $f_{*}$ from $-f_{*}$, we obtain
the desired lower bound using (8). ∎

###  2.3 Integration

In this section we prove the result of Theorem 1b for numerical integration
and give an example of an (asymptotically) optimal algorithm.

###### Proof.

For the upper bound, we simply consider the linear algorithm

$S_{P}^{*}:W^{s}_{p}(\Omega)\to\mathbb{R},\quad f\mapsto
S_{P}^{*}(f)=\int_{\Omega}S_{P}(f)(x)\,{\rm d}x$

with $S_{P}(f)\in L_{q}(\Omega)\subset L_{1}(\Omega)$ as in the previous
sections and observe that

$\Big{|}\int_{\Omega}f(x)~{}{\rm
d}x-S_{P}^{*}(f)\Big{|}\leq\|f-S_{P}(f)\|_{L_{1}(\Omega)}.$

In order to prove the lower bound, it suffices to note that the fooling
functions $f_{\ast}$ in Section 2.1 and Section 2.2 are nonnegative and thus
$\int f_{\ast}:=\int_{\Omega}f_{\ast}(x){\rm
d}x=\|f_{\ast}\|_{L_{1}(\Omega)}$. Since any algorithm of the form (3)
satisfies $S_{P}(f_{*})=S_{P}(-f_{*})$, we get

$\begin{split}e\big{(}P,{\rm
INT},W_{p}^{s}(\Omega)\big{)}\,&=\,\inf_{S_{P}}\sup_{\|f\|_{W^{s}_{p}(\Omega)}\leq
1}\big{|}S_{P}(f)-{\textstyle\int}f\big{|}\\\
&\geq\,\inf_{u\in\mathbb{R}}\,\max\left\\{\big{|}u-{\textstyle\int}f_{*}\big{|},\big{|}u+{\textstyle\int}f_{*}\big{|}\right\\}\geq\,{\textstyle\int}f_{\ast}\end{split}$

and thus the same lower bound as in (16) for $q=1$. ∎

If $p=2$ and $s>d/2$, Theorem 1 yields $e(P,{\rm
INT},W^{s}_{2}(\Omega))\asymp\|\operatorname{dist}(\cdot,P)\|_{L_{2s}(\Omega)}^{s}$
and this especially holds for the algorithm attaining the infimum in (2),
which we describe in the following. In this case, $W^{s}_{2}(\Omega)$ is a
Hilbert space consisting of functions on $\Omega$ such that we have the
continuous embedding $W^{s}_{2}(\Omega)\hookrightarrow C(\Omega)$. In
particular, $W^{s}_{2}(\Omega)$ is a reproducing kernel Hilbert space (RKHS),
see e.g. Aronszajn [3] for a definition and properties.

To any RKHS $(H,\langle\cdot,\cdot\rangle_{H})$ on $\Omega$ there corresponds
a symmetric and positive definite mapping, a kernel,
$K\colon\Omega\times\Omega\to\mathbb{R}$ such that if $x\in\Omega$, we have
$K(x,\cdot)\in H$ and the reproducing property $f(x)=\langle
f,K(x,\cdot)\rangle_{H}$ holds for all $f\in H$. A theorem due to Riesz yields
that every continuous linear functional $\ell\colon H\to\mathbb{R}$ can be
represented by a function $h_{\ell}\in H$. In fact, one has
$h_{\ell}(x)=\langle h_{\ell},K(x,\cdot)\rangle_{H}=\ell(K(x,\cdot))$ for
every $x\in\Omega$.

To be more concrete, set $H=W^{s}_{2}(\Omega)$, and denote the corresponding
kernel by $K_{s}$. Because of the embedding $W^{s}_{2}(\Omega)\hookrightarrow
C(\Omega)$ the integration functional $\int\colon
W^{s}_{2}(\Omega)\to\mathbb{R}$ is continuous, and, by the above, it is
represented by the function $h(\cdot)=\int_{\Omega}K_{s}(x,\cdot)\,{\rm d}x\in
W^{s}_{2}(\Omega)$. For a point set $P=\\{x_{1},\ldots,x_{n}\\}\subset\Omega$
and a linear algorithm $S_{P}\colon f\mapsto\sum_{i=1}^{n}w_{i}f(x_{i})$ with
weights $w=(w_{1},\ldots,w_{n})\in\mathbb{R}^{n}$ a well-known expression for
the worst-case error of $S_{P}$ on $W^{s}_{2}(\Omega)$ is available (see e.g.
(9.31) in [25]). It reads

$\sup_{\|f\|_{W^{s}_{2}(\Omega)}\leq 1}\Bigl{|}\int_{\Omega}f(x){\rm
d}x-S_{P}(f)\Bigr{|}^{2}=\langle w,\mathbf{K}w\rangle-2\langle w,b\rangle+c,$
(17)

where the matrix $\mathbf{K}:=\bigl{(}K_{s}(x_{i},x_{j})\bigr{)}_{i,j=1}^{n}$
is positive semi-definite, $b:=\bigl{(}\int_{\Omega}K_{s}(x,x_{i}){\rm
d}x\bigr{)}_{i=1}^{n}$, and $c:=\int_{\Omega}\int_{\Omega}K_{s}(x,y){\rm
d}x{\rm d}y$. Finding the optimal weights
$w^{\ast}=(w_{1}^{\ast},\ldots,w_{n}^{\ast})$ and thus the optimal (linear)
algorithm given $P$ is easy in this case. As a function of the weights, the
expression (17) is convex and therefore optimal weights are given by any
solution of

$\mathbf{K}w^{\ast}=b.$

Therefore, the knowledge of the kernel $K_{s}$ permits a computation of (an
approximation of) the optimal (linear) algorithm for numerical integration in
Theorem 1.

For obtaining the kernel $K_{s}$, we equip the Sobolev space
$W^{s}_{2}(\Omega)$ with the equivalent norm
$\|f\|^{\ast}_{W^{s}_{2}(\Omega)}:=\inf\big{\\{}\|g\|_{W^{s}_{2}(\mathbb{R}^{d})}\colon
g|_{\Omega}=f\big{\\}}$, where the equivalence is due Lemma 8. Then, Theorem 5
in [3] yields that the reproducing kernel $K_{s}$ of $W^{s}_{2}(\Omega)$ is
the restriction of the reproducing kernel $K_{d,s}$ of
$W^{s}_{2}(\mathbb{R}^{d})$ to $\Omega\times\Omega$, that is
$K_{s}(x,y)=K_{d,s}(x,y)$ for $x,y\in\Omega$.

An explicit form of $K_{d,s}$ can be found in Theorem 1 of Novak, Ullrich,
Woźniakowski and Zhang [23], which states that

$K_{d,s}(x,y)=\int_{\mathbb{R}^{d}}\frac{\exp\big{(}2\pi i\langle
x-y,u\rangle\big{)}}{1+\sum_{0<|\alpha|\leq s}\prod_{j=1}^{d}(2\pi
u_{j})^{2\alpha_{j}}}\,{\rm d}u,\quad\text{for }x,y\in\mathbb{R}^{d}.$

###  2.4 A first example

We illustrate the advantage of the characterization of optimal points in
Corollary 1 compared to conditions involving the covering radius. To this end,
consider $n$-point sets $P_{n}$ on a bounded convex domain $\Omega$. How large
can the largest hole admist $P_{n}$ be for this to be still optimal as a
sampling set for $L_{q}$-approximation of $W^{s}_{p}(\Omega)$-functions?

Assume that for each $n$ the ball $B_{n}:=B(y_{n},r_{n})$ with
$y_{n}\in\Omega$ and $r_{n}>0$ does not contain any points of $P_{n}$ and that
the points of $P_{n}$ cover $\Omega\setminus B_{n}$ nicely, i.e., the covering
radius of $P_{n}$ in $\Omega\setminus B_{n}$ is of order $n^{-1/d}$. Then we
have

$\int_{\Omega}\operatorname{dist}(x,P_{n})^{\gamma}~{}{\rm
d}x\,\preccurlyeq\,n^{-\gamma/d}+r_{n}^{\gamma+d}\quad\text{for all
}0<\gamma<\infty.$

Rearranging, this means that

$r_{n}\preccurlyeq
n^{-1/d+1/(\gamma+d)}\quad\text{implies}\quad\|\operatorname{dist}(\cdot,P_{n})\|_{L_{\gamma}(\Omega)}\preccurlyeq
n^{-1/d}.$ (18)

This condition is also necessary since
$\operatorname{dist}(\cdot,P_{n})\succcurlyeq r_{n}$ on $\Omega\cap
B(x_{n},\frac{r_{n}}{2})$, which is of volume $\asymp r_{n}^{d}$ due to the
interior cone condition, and thus

$\int_{\Omega}\operatorname{dist}(x,P_{n})^{\gamma}~{}{\rm
d}x\,\succcurlyeq\,r_{n}^{\gamma+d}.$

Letting $1\leq q<p\leq\infty$ and $\gamma$ as above, we obtain from Corollary
1 that $(P_{n})$ is asymptotically optimal for $L_{q}$-approximation on
$W_{p}^{s}(\Omega)$ if and only if

$r_{n}\preccurlyeq n^{-1/d+1/(\gamma+d)}.$ (19)

This means that the radius of the largest hole is allowed to exceed the
optimal covering radius $n^{-1/d}$ by the polynomial factor
$n^{1/(\gamma+d)}$. We also refer to [4, Theorem 1.2], where the necessity of
condition (19) has been observed for numerical integration on the sphere.

##  3 The optimality of random points

In the following we give the proof of Proposition 1. First, we derive a strong
asymptotic result from a theorem due to Cohort [6], which he obtained in the
context of random quantizers. Related work may be found in Graf and Luschgy
[13, Section 9] and [37].

######  Proposition 3.

Let $0<\gamma<\infty$ and $X_{1},X_{2},\ldots$ be independent and uniformly
distributed random vectors on a bounded domain $\Omega\subset\mathbb{R}^{d}$
which satisfies an interior cone condition. Consider the random $n$-point set
$P_{n}=\\{X_{1},\ldots,X_{n}\\}$. Then we have for all $0<p<\infty$ that

$n^{\gamma/d}\frac{1}{\operatorname{vol}(\Omega)}\int_{\Omega}\operatorname{dist}(x,P_{n})^{\gamma}{\rm
d}x\,\xrightarrow{\text{a.s.\,and in
}L_{p}}\,\left(\frac{\operatorname{vol}(\Omega)}{\operatorname{vol}\bigl{(}B(0,1)\bigr{)}}\right)^{\gamma/d}\Gamma\Bigl{(}1+\frac{\gamma}{d}\Bigr{)}.$

###### Proof.

We apply Theorem 1 and Theorem 2 in [6] and let $\mu=\nu$ be the uniform
distribution on $\Omega$, i.e., these measures have densities
$f=g=\frac{1}{\operatorname{vol}(\Omega)}\boldsymbol{1}_{\Omega}$, with
$\boldsymbol{1}_{\Omega}$ being the indicator function of $\Omega$. As Cohort
remarks in Section 2, assumption T2.1 is satisfied for bounded probability
density functions. Clearly, T1.2 and T2.3 are satisfied as well. For checking
assumptions T1.1 and T2.2, we note that the interior cone condition yields a
constant $c_{\Omega}>0$ such that for every $x\in\Omega$ and every
$0<\varrho\leq 1+\sup_{x\in\Omega}\|x\|_{2}$ we have
$\operatorname{vol}\bigl{(}B(x,\varrho)\cap\Omega\bigr{)}\geq
c_{\Omega}\operatorname{vol}\bigl{(}B(x,\varrho)\bigr{)}$. Since $\Omega$ is
bounded, assumptions T1.1 and T2.2 are validated and Theorems 1 and 2 can be
applied. Clearly, since convergence in $L_{p}$ implies convergence in $L_{q}$
for all $q<p$, the condition $p\in\mathbb{N}\setminus\\{1\\}$ in [6, Theorem
1] is obsolete. ∎

Regarding the asymptotic constant, let us note that if $\Omega$ is a centrally
symmetric convex body and $B(0,1)$ is the maximal volume ellipsoid inside
$\Omega$, the quantity
$\bigl{(}\operatorname{vol}(\Omega)/\operatorname{vol}\bigl{(}B(0,1)\bigr{)}\bigr{)}^{1/d}$
is known as the volume ratio of $\Omega$, which plays an important role in
Banach space geometry, see e.g. Szarek and Tomczak-Jaegermann [31]. Further,
as $\gamma\to\infty$ the quantity
$\bigl{(}\Gamma(1+\frac{\gamma}{d})\bigr{)}^{1/\gamma}$ tends to infinity,
which is compatible to the fact that the $L_{\infty}$-norm of
$\operatorname{dist}(\cdot,P_{n})$ is typically of larger order than
$n^{-1/d}$.

###### Proof of Proposition 1.

Let $0<\gamma<\infty$. By Lemma 3 a bounded convex domain satisfies an
interior cone condition. We set $p=\alpha/\gamma$ and obtain from Proposition
3 that
$n^{\gamma/d}\cdot\|\operatorname{dist}(\cdot,P_{n})\|_{L_{\gamma}(\Omega)}^{\gamma}$
converges in $L_{p}$ to a positive constant, which implies that also
$n^{\alpha/d}\cdot\mathbb{E}\,\|\operatorname{dist}(\cdot,P_{n})\|_{L_{\gamma}(\Omega)}^{\alpha}$
converges to a positive constant. This completes the proof.

The case $\gamma=\infty$ is well known. It is strongly connected to the so-
called coupon collector’s problem, which asks for the number of coupons
(points) that a collector has to draw in order to obtain a complete collection
(hit every set in a diameter-bounded equal volume partition of $\Omega$).
Using that $\Omega$ satisfies an interior cone condition, the stated result
e.g. follows from Theorems 2.1 and 2.2 in Reznikov and Saff [27] with
$\Phi(r)=r^{d}$. ∎

######  Remark 6.

Proposition 3 extends to probability distributions different from the uniform
distribution. Under certain conditions, it also allows for the sampling
distribution to differ from the distribution with respect to which the
$L_{\gamma}$-norm of $\operatorname{dist}(\cdot,P_{n})$ is computed.

##  4 Extensions to Triebel-Lizorkin spaces

In this section we discuss how to extend Theorem 1 to a wider range of
function spaces. To that end, we consider the Triebel-Lizorkin spaces
$F^{s}_{p\tau}(\Omega)$ for $0<p<\infty$, $0<\tau\leq\infty$ and $s>d/p$ as
defined e.g. in [22]. We refrain from reproducing the definition and simply
note that this family covers a variety of interesting spaces:

  * •

For $\tau=2$ and $1<p<\infty$, we obtain the fractional Sobolev space (or
Bessel potential space) $H^{s}_{p}(\Omega)$, see e.g. [22]. If additionally
$s\in\mathbb{N}$, we arrive at the classical Sobolev spaces
$W^{s}_{p}(\Omega)$ as defined in Section 1.

  * •

For $s\not\in\mathbb{N}$, $1\leq p<\infty$ and $\tau=p$, we obtain the
Sobolev-Slobodeckij space $W^{s}_{p}(\Omega)$ of fractional smoothness, see
e.g. [8] and note that $F^{s}_{pp}(\Omega)$ is the Besov space
$B^{s}_{pp}(\Omega)$.

We also want to discuss the Hölder spaces $C^{s}(\Omega)$, which are not
included in this scale. For $s\in\mathbb{N}$, the Hölder space $C^{s}(\Omega)$
is the space of all $s$ times continuously differentiable functions with

$\|f\|_{C^{s}(\Omega)}:=\max_{|\alpha|\leq
s}\,\sup_{x\in\Omega}\,|D^{\alpha}f(x)|<\infty.$

For $s\not\in\mathbb{N}$, it is defined as the space of functions $f\in
C^{\lfloor s\rfloor}(\Omega)$ with

$|f|_{C^{s}(\Omega)}:=\max_{|\alpha|=\lfloor s\rfloor}\,\sup_{x\neq
y}\,\frac{|D^{\alpha}f(x)-D^{\alpha}f(y)|}{\|x-y\|^{\\{s\\}}}<\infty,$ (20)

where $s=\lfloor s\rfloor+\\{s\\}$ with $0<\\{s\\}<1$. It is equipped with the
norm $\|\cdot\|_{C^{\lfloor s\rfloor}(\Omega)}+|\cdot|_{C^{s}(\Omega)}$.

Note that in this article equality between function spaces is meant up to
equivalence of norms and the equivalence constants vanish in the asymptotic
notation. Further, all mentioned spaces are continuously embedded in
$C(\Omega)$. We obtain the following extension of our results on
$L_{q}$-approximation.

######  Theorem 2.

Theorem 1, Corollary 1 and Corollary 2 remain valid if we admit arbitrary real
parameters $0<p,q,\tau\leq\infty$ and $s>d/p$ and replace $W_{p}^{s}(\Omega)$
either by $C^{s}(\Omega)$ for $p=\infty$ or by $F^{s}_{p\tau}(\Omega)$ for
$p<\infty$.

For the proof, let us first note that the analogues of Corollary 1 and
Corollary 2 immediately follow from the analogue of Theorem 1a if we employ
(4) and Proposition 1. Moreover, the extension of Theorem 1a to the case
$C^{s}(\Omega)$ for $s\in\mathbb{N}$ is already included in Section 2. Namely,
the upper bound is immediate from the continuous embedding
$C^{s}(\Omega)\hookrightarrow W_{\infty}^{s}(\Omega)$. The lower bound holds
since our fooling functions $f_{\ast}$ for $W_{\infty}^{s}(\Omega)$ are smooth
and non-negative. For the remaining cases, we follow the lines of the proof of
Theorem 1. We only discuss the necessary changes.

###### Proof of the upper bounds.

It suffices to consider the case $\tau=\infty$, since
$F^{s}_{p\tau_{1}}(\Omega)\hookrightarrow F^{s}_{p\tau_{2}}(\Omega)$ for
$\tau_{1}\leq\tau_{2}$. We replace $|f|_{W_{p}^{s}(\Omega)}$ by the following
semi-(quasi-)norms:

  * •

For $p=\infty$ and $s\not\in\mathbb{N}$, we use the semi-norm
$|f|_{C^{s}(\Omega)}$ as defined in (20).

  * •

For $p<\infty$, we use a semi-(quasi-)norm which is defined via the means

$(d_{t}^{M,\Omega}f)(x):=t^{-d}\int_{V^{M}_{\Omega}(x,t)}\bigl{|}(\Delta_{h,\Omega}^{M}f)(x)\bigr{|}\,\text{d}h,$

where $M:=\lfloor s+1\rfloor$, $\Delta_{h,\Omega}^{M}$ is an
$M^{\rm{th}}$-order difference operator restricted to $\Omega$ and
$V^{M}_{\Omega}(x,t)$ is the set of directions $h\in\mathbb{R}^{d}$ of length
less than $t>0$ with $x+ah\in\Omega$ for all $0\leq a\leq M$. That is,
$(d_{t}^{M,\Omega}f)(x)$ is an averaged mean of the $M^{\rm{th}}$-order
differences of $f$ around $x$. Putting

$|f|_{F^{s}_{p\infty}(\Omega)}:=\bigg{\|}\sup_{0\leq t\leq
1}\frac{(d_{t}^{M,\Omega}f)(\cdot)}{t^{s}}\bigg{\|}_{L_{p}(\Omega)},$

it is known that we then have the equality $F^{s}_{p\infty}(\Omega)=\\{f\in
L_{\infty}(\Omega)\colon|f|_{F^{s}_{p\infty}(\Omega)}<\infty\\}$ and
$\|\cdot\|_{L_{\max\\{p,1\\}}(\Omega)}+|\cdot|_{F^{s}_{p\infty}(\Omega)}$ is
an equivalent quasi-norm, see Proposition 6 in [22] and set $u=1$ as well as
$r=\infty$. The same is true for $\Omega=\mathbb{R}^{d}$.

It is readily verified that these semi-(quasi-)norms have the following
scaling property. If $T\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ is of the form
$T(x)=\varrho^{-1}x+x_{0}$ with $\varrho\leq 1$ and $x_{0}\in\mathbb{R}^{d}$
and $f\in F^{s}_{p\infty}(\Omega)$ or $f\in C^{s}(\Omega)$, then $g=f\circ
T^{-1}$ satisfies

$|g|_{F^{s}_{p\infty}(T\Omega)}\leq\varrho^{s-d/p}|f|_{F^{s}_{p\infty}(\Omega)},\qquad|g|_{C^{s}(T\Omega)}=\varrho^{s}|f|_{C^{s}(\Omega)},\quad\text{respectively.}$
(21)

Lemma 8 holds without changes for the spaces $F^{s}_{p\tau}(\Omega)$ and
$C^{s}(\Omega)$, see Rychkov [28], where we note that
$C^{s}(\Omega)=B^{s}_{\infty\infty}(\Omega)$ for $s\not\in\mathbb{N}$. If we
use [22, Corollary 11] (for $p<\infty$) and [10, Theorem 6.1] (for $p=\infty$)
instead of [19, Lemma 1.1.11] and the scaling properties (21), we see that
Lemma 9 concerning polynomial approximation on cubes remains valid under the
modifications of Theorem 2. Thus, also Lemma 10 defies our modifications. It
only remains to note that the semi-norm $|\cdot|_{F^{s}_{p\infty}(\Omega)}$
behaves equally well with respect to an efficient covering. Analogous to (7),
we have

$\sum_{j=1}^{N}|f|^{p}_{F^{s}_{p\infty}(Q_{j})}=\int_{\mathbb{R}^{d}}\left(\sup_{0\leq
t\leq
1}\frac{(d_{t}^{M,Q_{j}}f)(x)}{t^{s}}\right)^{p}\sum_{j=1}^{N}\mathbbm{1}_{Q_{j}}(x){\rm
d}x\leq c_{7}|f|^{p}_{F^{s}_{p\infty}(\mathbb{R}^{d})}\leq c_{8}$ (22)

since $d_{t}^{M,Q_{j}}f(x)\leq d_{t}^{M,\mathbb{R}^{d}}f(x)$ for every
$x\in\mathbb{R}^{d}$. With these preparations at hand, we may copy the proofs
of Section 2. ∎

###### Proof of the lower bounds.

Also the lower bound for the cases $q\geq p$ and $q<p=\infty$ can be copied.
The scaling properties (9) for $F^{s}_{p\tau}$ may be obtained from
Proposition 2.3.1/1 in [11] and the translation-invariance of the quasi-norm.
The lower bound in the case $q<p<\infty$ requires different ideas as we cannot
establish
$\left\|\sum_{i}\varphi_{i}\right\|_{F^{s}_{p\tau}(\mathbb{R}^{d})}^{p}\preccurlyeq\sum_{i}\|\varphi_{i}\|^{p}_{F^{s}_{p\tau}(\mathbb{R}^{d})}$
for general disjointly supported $\varphi_{i}$, as used in (14) for the
Sobolev spaces. For optimal point sets, this problem does not exist as we may
consider bumps $\varphi_{i}$ which are supported in balls of the same radius
which enables the use of localization methods, see [22]. For general point
sets, a remedy can be provided with the help of atomic decompositions of the
spaces $F^{s}_{p\tau}(\Omega)$ as treated by Triebel [32].

Let $y_{i}$, $d_{i}$ and $B_{i}$ be as in Proposition 2. Let $K>s$ be an
integer and let $Q$ be the cube of sidelength $1$ which is centered at the
origin. Let $\psi\in C^{\infty}(\mathbb{R}^{d})$ be non-negative with
$\mathrm{supp}\,\psi\subset Q$ such that $\psi(0)>0$ and
$\|D^{\alpha}\psi\|_{\infty}\leq 1$ for all $\alpha\in\mathbb{N}_{0}^{d}$ with
$|\alpha|\leq K$. The exact choice of the function $\psi$ is not important for
our argument. According to Definition 13.3 in [32] the function

$\psi_{\nu m}(\cdot)=2^{-\nu(s-d/p)}\psi(2^{\nu}\cdot-m)\quad\text{where
}\nu\in\mathbb{N}_{0},\ m\in\mathbb{Z}^{d},$

is an $(s,p)_{K,-1}$-atom supported in $Q_{\nu m}$, the cube with center
$2^{-\nu}m$ and sidelength $2^{-\nu}$. We choose $m_{i}\in\mathbb{Z}^{d}$ and
$\nu_{i}\in\mathbb{N}_{0}$ with $2^{-\nu_{i}}\asymp d_{i}$ such that the
dyadic cube $Q_{i}^{*}:=Q_{\nu_{i}m_{i}}$ is contained in $B_{i}$. Set

$f:=\sum_{i=1}^{N}\lambda_{i}\psi_{i},\quad\text{where
}\lambda_{i}:=2^{-\nu_{i}\beta}\text{ with }\beta=(\gamma+d)/p.$

This function is supported in $\Omega$ and satisfies $f|_{P}=0$. Also,
$\|f\|_{F^{s}_{p\tau}(\Omega)}=\|f\|_{F^{s}_{p\tau}(\mathbb{R}^{d})}$ and by
[32, Theorem 13.8],

$\|f\|_{F^{s}_{p\tau}(\mathbb{R}^{d})}^{p}\lesssim\|\lambda\|_{f_{p\tau}}^{p}=\int_{\mathbb{R}^{d}}\Big{(}\sum_{i=1}^{N}|\lambda_{i}2^{\nu_{i}d/p}\mathbf{1}_{Q_{i}^{*}}(x)|^{\tau}\Big{)}^{p/\tau}{\rm
d}x,$

where the implicit constant does not depend on the balls $B_{i}$ and
$f_{p\tau}$ is a quasi-normed space of sequences. For every
$x\in\mathbb{R}^{d}$ only one summand is not equal to zero and since
$\mathrm{vol}(Q_{i}^{*})=2^{-\nu_{i}d}$,

$\|f\|_{F^{s}_{p\tau}(\mathbb{R}^{d})}^{p}\lesssim\sum_{i=1}^{N}\int_{Q_{i}^{*}}(2^{-\nu_{i}})^{\beta
p-d}\mathbf{1}_{Q_{i}^{*}}(x){\rm d}x=\sum_{i=1}^{N}(2^{-\nu_{i}})^{\beta p}.$

As $\beta p=\gamma+d$ and $2^{-\nu_{i}}\asymp d_{i}$, we arrive at

$\|f\|_{F^{s}_{p\tau}(\Omega)}^{p}\lesssim\sum_{i=1}^{N}d_{i}^{\gamma+d}.$

Using a substitution we have

$\|f\|_{L_{q}(\Omega)}^{q}=\sum_{i=1}^{N}\int_{Q_{i}^{*}}(2^{-\nu_{i}})^{\beta
q}\psi_{i}(x)^{q}{\rm d}x=\sum_{i=1}^{N}(2^{-\nu_{i}})^{\beta q+sq-
dq/p+d}\int_{2Q}\psi(x)^{q}{\rm d}x.$

Since $\beta q+sq=\gamma+dq/p$ we have

$\|f\|_{L_{q}(\Omega)}^{q}\asymp\sum_{i=1}^{N}d_{i}^{\gamma+d}.$

It follows that the normalized function
$f_{*}=f/\|f\|_{F^{s}_{p\tau}(\Omega)}$ satisfies

$\|f_{*}\|_{L_{q}(\Omega)}=\frac{\|f\|_{L_{q}(\Omega)}}{\|f\|_{F^{s}_{p\tau}(\Omega)}}\gtrsim\Big{(}\sum_{i=1}^{N}d_{i}^{\gamma+d}\Big{)}^{1/q-1/p}\gtrsim\Big{(}\int_{\Omega}\operatorname{dist}(x,P)^{\gamma}{\rm
d}x\Big{)}^{s/\gamma},$

where the last inequality derives from (15). Now the fooling function
$f_{\ast}$ yields the lower bound analogous to (8). We get the lower bound for
the integration problem as the function $f_{*}$ is non-negative and thus
$\|f\|_{L_{1}(\Omega)}=\int_{\Omega}f(x){\rm d}x$. ∎

Let us conclude with a few remarks on further extensions of our result.

######  Remark 7 (More general domains, part 2).

We only used that $\Omega$ is a bounded Lipschitz domain in order to extend
functions on $\Omega$ to functions on $\mathbb{R}^{d}$ without significant
change of the norm. It is not hard to check that our results are valid for all
bounded measurable sets $\Omega$ satisfying a strong local cone condition as
in Lemma 6 if the function spaces on $\Omega$ are defined via restriction of
the corresponding function spaces on $\mathbb{R}^{d}$, i.e.,

$A(\Omega):=\\{f|_{\Omega}\colon f\in
A(\mathbb{R}^{d})\\},\qquad\|g\|_{A(\Omega)}:=\inf_{f\in
A(\mathbb{R}^{d})\colon f|_{\Omega}=g}\|f\|_{A(\mathbb{R}^{d})}$

for $A\in\\{W_{p}^{s},F^{s}_{p\tau},C^{s}\\}$. By Lemma 8 (and its analogues),
these spaces coincide with the spaces from above (in the sense of equivalent
norms) if $\Omega$ is a bounded Lipschitz domain.

######  Remark 8 (Besov spaces).

It remains open whether Theorem 2 carries over also to the scale of Besov
spaces $B^{s}_{p\tau}(\Omega),$ where $0<p,\tau\leq\infty$ and $s>d/p$. The
upper bounds are complicated by finding an analogue of (22). Novak and Triebel
[22] avoid this employing interpolation, which may also be used here in order
to treat the case $q\geq p$, but for $q<p$ different methods may be required.
For the lower bound the situation is similar to the $F$-spaces. We leave the
extension of Theorem 2 to Besov spaces for future research.

######  Remark 9 (Functions with zero boundary condition).

Since all our fooling functions are supported in the open set $\Omega$, all
our results hold without changes for the smaller spaces of functions
satisfying zero boundary conditions.

#### Acknowledgement.

We thank Erich Novak for fruitful discussions about polynomial reproduction
and both Winfried Sickel and Mario Ullrich for pointing us toward
characterization of $F$-spaces in terms of wavelets and atoms. The authors
were supported by the Austrian Science Fund (FWF) through projects F5513-N26
(DK, MS), which is part of the Special Research Program “Quasi-Monte Carlo
Methods: Theory and Applications”, and P32405 “Asymptotic Geometric Analysis
and Applications” (MS).

## References

  * [1] R. A. Adams and J. J. F. Fournier.  Sobolev spaces, volume 140 of Pure and Applied Mathematics.  Elsevier/Academic Press, Amsterdam, second edition, 2003.
  * [2] R. Arcangéli, M. C. López de Silanes, and J. J. Torrens.  An extension of a bound for functions in Sobolev spaces, with applications to $(m,s)$-spline interpolation and smoothing.  Numer. Math., 107(2):181–211, 2007.
  * [3] N. Aronszajn.  Theory of reproducing kernels.  Trans. Amer. Math. Soc., 68:337–404, 1950.
  * [4] J. S. Brauchart, J. Dick, E. B. Saff, I. H. Sloan, Y. G. Wang, and R. S. Womersley.  Covering of spheres by spherical caps and worst-case error for equal weight cubature in Sobolev spaces.  J. Math. Anal. Appl., 431(2):782–811, 2015.
  * [5] P. G. Ciarlet.  The finite element method for elliptic problems.  Cambridge University Press, Amsterdam, North-Holland, 1978.
  * [6] P. Cohort.  Limit theorems for random normalized distortion.  Ann. Appl. Probab., 14(1):118–143, 2004.
  * [7] S. Dekel and D. Leviatan.  Whitney estimates for convex domains with applications to multivariate piecewise polynomial approximation.  Found. Comput. Math., 4(4):345–368, 2004.
  * [8] R. A. DeVore and R. C. Sharpley.  Besov spaces on domains in $\mathbb{R}^{d}$.  Trans. Amer. Math. Soc., 335(2):843–864, 1993.
  * [9] J. Duchon.  Sur l’erreur d’interpolation des fonctions de plusieurs variables par les $D^{m}$-splines.  RAIRO Anal. Numér., 12(4):325–334, vi, 1978.
  * [10] T. Dupont and R. Scott.  Polynomial Approximation of Functions in Sobolev Spaces.  Math. Comp., 34(150):441–463, 1980.
  * [11] D. E. Edmunds and H. Triebel.  Function spaces, entropy numbers, differential operators, volume 120 of Cambridge Tracts in Mathematics.  Cambridge University Press, Cambridge, 1996.
  * [12] M. Ehler, M. Graef, and C. J. Oates.  Optimal Monte Carlo integration on closed manifolds.  Statistics and Computing, 29:1203–1214, 2019.
  * [13] S. Graf and H. Luschgy.  Foundations of quantization for probability distributions, volume 1730 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 2000.
  * [14] S. Heinrich.  Random approximation in numerical analysis.  In K. D. Bierstedt and et al., editors, Functional Analysis, pages 123–171. Dekker, New York, 1994.
  * [15] A. Hinrichs, D. Krieg, E. Novak, J. Prochno, and M. Ullrich.  Random sections of ellipsoids and the power of random information.  arXiv preprints, arXiv:1901.06639, 2019.
  * [16] A. Hinrichs, D. Krieg, E. Novak, J. Prochno, and M. Ullrich.  On the power of random information.  In F. J. Hickernell and P. Kritzer, editors, Multivariate Algorithms and Information-Based Complexity, pages 43–64. De Gruyter, Berlin/Boston, 2020.
  * [17] A. Hinrichs, D. Krieg, E. Novak, and J. Vybíral.  Lower bounds for the error of quadrature formulas for Hilbert spaces.  arXiv preprints, arXiv:2004.00274, 2020.
  * [18] D. Krieg and M. Ullrich.  Function values are enough for $L_{2}$-approximation.  arXiv preprints, arXiv:1905.02516, 2019.
  * [19] V. G. Maz’ya.  Sobolev spaces.  Springer Series in Soviet Mathematics. Springer-Verlag, Berlin, 1985.  Translated from the Russian by T. O. Shaposhnikova.
  * [20] H. N. Mhaskar.  Eignets for function approximation on manifolds.  Appl. Comput. Harmon. Anal., 29(1):63–87, 2010.
  * [21] F. J. Narcowich, J. D. Ward, and H. Wendland.  Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting.  Math. Comp., 74(250):743–763, 2004.
  * [22] E. Novak and H. Triebel.  Function spaces in Lipschitz domains and optimal rates of convergence for sampling.  Constr. Approx., 23:325–350, 2006.
  * [23] E. Novak, M. Ullrich, H. Woźniakowski, and S. Zhang.  Reproducing kernels of Sobolev spaces on $\mathbb{R}^{d}$ and applications to embedding constants and tractability.  Anal. Appl. (Singap.), 16(5):693–715, 2018.
  * [24] E. Novak and H. Woźniakowski.  Tractability of multivariate problems. Vol. 1: Linear information, volume 6 of EMS Tracts in Mathematics.  European Mathematical Society (EMS), Zürich, 2008.
  * [25] E. Novak and H. Woźniakowski.  Tractability of multivariate problems. Volume II: Standard information for functionals, volume 12 of EMS Tracts in Mathematics.  European Mathematical Society (EMS), Zürich, 2010.
  * [26] G. Pagès.  A space quantization method for numerical integration.  J. Comput. Appl. Math., 89(1):1–38, 1998.
  * [27] A. Reznikov and E. B. Saff.  The covering radius of randomly distributed points on a manifold.  Int. Math. Res. Not. IMRN, 2016(19):6065–6094, 2016.
  * [28] V. S. Rychkov.  On restrictions and extensions of the Besov and Triebel-Lizorkin spaces with respect to Lipschitz domains.  J. London Math. Soc. (2), 60(1):237–257, 1999.
  * [29] E. M. Stein.  Singular integrals and differentiability properties of functions.  Princeton University Press, Princeton, New Jersey, 1971.
  * [30] A. G. Suharev.  Optimal formulas of numerical integration for some classes of functions of several variables.  Dokl. Akad. Nauk SSSR, 246(2):282–285, 1979.
  * [31] S. Szarek and N. Tomczak-Jaegermann.  On nearly Euclidean decomposition for some classes of Banach spaces.  Compositio Math., 40(3):367–385, 1980.
  * [32] H. Triebel.  Fractals and spectra.  Birkhäuser Verlag, Basel, 2011.
  * [33] M. Ullrich.  On the worst-case error of least squares algorithms for $L_{2}$-approximation with high probability.  J. Complex., 60, 2020.
  * [34] Wayne State University.  Classroom Notes: Every convex function is locally Lipschitz.  Amer. Math. Monthly, 79:1121–1124, 1972.
  * [35] H. Wendland.  Scattered data approximation, volume 17 of Cambridge Monographs on Applied and Computational Mathematics.  Cambridge University Press, Cambridge, 2005.
  * [36] Z. M. Wu and R. Schaback.  Local error estimates for radial basis function interpolation of scattered data.  IMA J. Numer. Anal., 13(1):13–27, 1993.
  * [37] J. E. Yukich.  Limit theorems for multi-dimensional random quantizers.  Electron. Commun. Probab., 13:507–517, 2008.