q h

Fig. 3.1 Ball in a cone.

Lemma 3.7 Suppose that C = C(x, ξ, θ, r ) is a cone de¬ned as in (3.1). Then for every

h ¤ r/(1 + sin θ ) the closed ball B = B(y, h sin θ) with center y = x + hξ and radius

h sin θ is contained in C(x, ξ, θ, r ). In particular, if z is a point from this ball then the whole

line segment x + t(z ’ x)/ z ’ x 2 , t ∈ [0, r ], is contained in the cone.

Proof Without restriction we can assume x = 0. If z ∈ B then z 2 ¤ z ’ y 2 + y 2 ¤

h sin θ + h ¤ r . Thus the ball B is contained in the larger ball around x with radius r and

it remains to show that it is contained in the correct segment. Suppose that this is not the

case. Then we can ¬nd a z ∈ B, z ∈ C, i.e. z T ξ < z 2 cos θ. This means that

h 2 sin2 θ ≥ z ’ y = z ’ hξ

2 2

2 2

=z + h 2 ’ 2hz T ξ > z + h 2 ’ 2h z cos θ,

2 2

2

2

which leads to the contradiction

0> z + h 2 (1 ’ sin2 θ) ’ 2h z cos θ

2

2

2

=z + h cos θ ’ 2h z cos θ

2 2 2

2

2

=( z ’ h cos θ ) ≥ 0.

2

2

To prove the norming-set property we will use the fact that a multivariate polynomial

reduces to a univariate polynomial when restricted to a line. Then we want to relate the

Chebychev norm of the univariate polynomial on a line segment to the Chebychev norm

of the multivariate polynomial on . To do this we have to ensure that the line segment is

completely contained in .

Theorem 3.8 Suppose ⊆ Rd is compact and satis¬es an interior cone condition with

radius r > 0 and angle θ ∈ (0, π/2). Let m ∈ N be ¬xed. Suppose h > 0 and the set X =

{x1 , . . . , x N } ⊆ satisfy

r sin θ

(1) h ¤ ,

4(1 + sin θ)m 2

(2) for every B(x, h) ⊆ there is a center x j ∈ X © B(x, h);

30 Local polynomial reproduction

then Z = {δx : x ∈ X } is a norming set for πm (Rd )| and the norm of the inverse of the

associated sampling operator is bounded by 2.

Proof Markov™s inequality for an algebraic polynomial p ∈ πm (R1 ) is given by

| p (t)| ¤ m 2 p L ∞ [’1,1] , t ∈ [’1, 1];

see for example Cheney [41]. A simple scaling argument shows for r > 0 and all p ∈

πm (R1 ) that

22

| p (t)| ¤ L ∞ [0,r ] , t ∈ [0, r ].

mp

r

Choose an arbitrary p ∈ πm (Rd ) with p L ∞ ( ) = 1. Since is compact there exists an

x ∈ with | p(x)| = p L ∞ ( ) = 1. As satis¬es an interior cone condition we can ¬nd

a ξ ∈ Rd with ξ 2 = 1 such that the cone C(x) := C(x, ξ, θ, r ) is completely contained

in . Because h/ sin θ ¤ r/(1 + sin θ) we can use Lemma 3.7 with h replaced by h/ sin θ

to see that B(y, h) ⊆ C(x) with y = x + (h/sin θ )ξ . For this y we ¬nd an x j ∈ X with

y ’ x j 2 ¤ h, i.e. x j ∈ B(y, h) ⊆ C(x). Thus the whole line segment

xj ’ x

x +t , t ∈ [0, r ],

xj ’ x 2

lies in C(x) ⊆ . If we ¬nally apply Markov™s inequality to

xj ’ x

p(t) := p x + t , t ∈ [0, r ],

xj ’ x 2

we see that

x’x j 2

| p(x) ’ p(x j )| ¤ | p (t)|dt

0

22

¤ x ’ xj m p L ∞ [0,r ]

2

r

2(1 + sin θ ) 2

¤h m p L∞( )

r sin θ

1

¤

2

by using x ’ x j 2 ¤ x ’ y + y ’ xj ¤ h + h/ sin θ. This shows that | p(x j )| ≥

2 2

1/2 and proves the theorem.

Note that in the case h = h X, condition (2) is automatically satis¬ed. However, setting

h = h X, is somewhat too strong for what we have in mind. An immediate consequence of

Theorems 3.4 and 3.8 is

Corollary 3.9 If X = {x1 , . . . , x N } ⊆ and h > 0 satisfy the conditions of Theorem 3.8

then there exist for every x ∈ |u j (x)| ¤ 2 and

real numbers u j (x) such that

u j (x) p(x j ) = p(x) for all p ∈ πm (R ).

d

3.3 Existence for regions with cone condition 31

Our ¬rst example of a region satisfying an interior cone condition is given by a ball. It is

an example where the constants are independent of the space dimension.

Lemma 3.10 Every ball with radius δ > 0 satis¬es an interior cone condition with radius

δ > 0 and angle θ = π/3.

Proof Without restriction we can assume that the ball is centered at zero. For every point x

in the ball we have to ¬nd a cone with prescribed radius and angle. For the center x = 0 we

can choose any direction to see that such a cone is indeed contained in the ball. For x = 0

we choose the direction ξ = ’x/ x 2 . A typical point on the cone is given by x + »y with

y 2 = 1, y T ξ ≥ cos π/3 = 1/2 and 0 ¤ » ¤ δ. For this point we ¬nd

x + »y =x + »2 ’ 2» x 2 ξ T y ¤ x + »2 ’ » x 2 .

2 2 2

2 2 2

The last expression equals x 2 ( x 2 ’ ») + »2 , which can be bounded by »2 ¤ δ 2 in the

case x 2 ¤ ». If » ¤ x 2 then we can transform the last expression to »(» ’ x 2 ) +

x 2 , which can be bounded by x 2 ¤ δ 2 . Thus x + »y is contained in the ball.

2 2

Corollary 3.11 De¬ne for m ∈ N

√

3

cm = .

√ (3.2)

4(2 + 3)m 2

If Y = {y1 , . . . , y M } ⊆ B = B(x0 , δ) satis¬es h Y,B ¤ cm δ then span{δx : x ∈ Y } is a norm-

ing set for πm (Rd )|B with norming constant c = 2. In particular, for every x ∈ there

|u j (x)| ¤ 2 and u j (x) p(y j ) = p(x) for all

exist real numbers u j (x) such that

p ∈ πm (R ).

d

While so far everything is still global, which means that we do not have any information

on whether the u j vanish, we now proceed to a local version. The main idea can be described

as follows. If satis¬es an interior cone condition then we can ¬nd for every x ∈ a cone

with vertex x that is completely contained in . Then we apply the global version given