k=1 j=1

and therefore as smooth as .

However, even if the smoothness of the approximant is governed by the smoothness of ,

numerical examples show that the effect of the scaling parameter on the “visual” smoothness

is more important. Too small a scaling parameter leads to a bumpy surface, while too large

a parameter results in a smoothed-out representation; see Figure 4.2.

4.2 Local polynomial reproduction by moving least squares

In the case m = 0 it is easy to bound the approximation error. We know that s f,X has the

representation (4.3), which shows immediately that the basis functions

’ xi )

δ (x

ai— (x) =

δ (x ’ x j )

j∈I (x)

|ai— (x)| = ai— (x) = 1. This gives the error bound

satisfy

| f (x) ’ s f,X (x)| ¤ 2 f ’ p L ∞ (B(x,δ)) .

For general m ∈ N we can draw conclusions on the approximation property by showing

that the moving least squares approximation provides local polynomial reproduction. This

needs a further assumption on the set of data sites. The general concept we are now going

to introduce will be essential in the whole of this book.

So far, we have only measured how well a set of data sites covers the domain . This is

done by means of h X, , which guarantees a data site x j within a distance h X, for every

x ∈ . Or, in other words, the largest ball in that does not contain a data site has radius

at most h X, .

4.2 Local polynomial reproduction by moving least squares 41

However, this covering should be achieved by as few data sites as possible.

De¬nition 4.6 The separation distance of X = {x1 , . . . , x N } is de¬ned by

xi ’ x j 2.

1

q X := min

2 i= j

A set X of data sites is said to be quasi-uniform with respect to a constant cqu > 0 if

q X ¤ h X, ¤ cqu q X . (4.8)

The separation distance gives the largest possible radius for two balls centered at different

data sites to be essentially disjoint. The de¬nition of quasi-uniformity has to be seen in the

context of more than one set of data sites. The idea is that a sequence of such sets is

considered such that the region is more and more ¬lled out. Then it is important that

condition (4.8) is satis¬ed by all sets in this sequence with the same constant cqu . For

example, if = [0, 1]d is the unit cube and X h = hZd © then obviously the separation

√

distance is given by q X = h/2 while the ¬ll distance is given by h X h , = ( d/2)h. Hence,

√

we have quasi-uniformity with cqu = d. We will discuss quasi-uniform sets in more detail

in Chapter 14.

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

angle θ ∈ (0, π/2) and radius r > 0. Fix m ∈ N. Let h 0 , C1 , and C2 denote the constants

from Theorem 3.14. Suppose that X = {x1 , . . . , x N } ⊆ satis¬es (4.8) and h X, ¤ h 0 . Let

δ = 2C2 h X, . Then the basis functions a — (x) from Corollary 4.4 provide local polynomial

j

reproduction, i.e.

a — (x) p(x j ) = p(x) for all p ∈ πm (Rd ), x ∈

N

(1) ,

j

j=1

|a — (x)|

N

¤ C1 ,

(2) j

j=1

(3) a — (x) = 0 if x ’ x j > C2 h X, ,

2

j

with certain constants C1 , C2 that can be derived explicitly.

Proof The ¬rst property follows from the construction process of moving least squares.

The third property is a consequence of the compact support of . By Corollary 4.4, a — is

j

supported in B(x j , δ), and δ has been chosen as 2C2 h X, . This shows that in particular

C2 = 2C2 . For the second property we have to work harder. We start with

1/2 1/2

1

|ai— (x)| ¤ |ai— (x)|2 ’ xi )

δ (x

δ (x ’ x i )

i∈I (x) i∈I (x) i∈I (x)

and bound each factor on the right-hand side separately, beginning with the ¬rst.

By Theorem 3.14 we know that there exists a set {u j } providing local polynomial repro-

duction. The function u j (x) vanishes if x ’ x j 2 > C2 h X, = δ/2. The minimal property

42 Moving least squares

of {a — } allows us the estimate

j

1 1

|ai— (x)|2 ¤ |u i (x)|2

δ (x ’ x i ) δ (x ’ x i )

i∈I (x) i∈ I (x)

1

¤ |u i (x)|2

min y∈B(0,1/2) (y)

i∈ I (x)

⎛ ⎞2

1 ⎝ |u i (x)|⎠

¤

min y∈B(0,1/2) (y)

i∈ I (x)

2

C1

¤ .

min y∈B(0,1/2) (y)

Here, we have used the notation I (x) = { j : x j ∈ B(x, δ/2)}. To bound the second factor

we ¬rst note that obviously

’ xi ) ¤ #I (x) L ∞ (Rd ) .

δ (x

i∈I (x)

To bound the number #I (x) of points in I (x) we use a packing argument. Any ball with

radius q X centered at x j is essentially disjoint to a ball centered at xk = x j of the same radius,

and all these balls with j ∈ I (x) are contained in a ball with radius q X + δ. Comparing the

volume of the union of the small balls with the volume of the large ball gives

#I (x) vol(B(0, 1)) q X ¤ vol(B(0, 1)) (δ + q X )d .

d

Using quasi-uniformity ¬nally leads to

#I (x) ¤ (1 + δ/q X )d ¤ (1 + 2C2 cqu )d .

It is important to recognize that we have an explicit estimate on the constant C2 , because

the latter determines the necessary scale factor δ. However, numerical tests show that the

estimate we derived in Theorem 3.14 is rather pessimistic. One can often get away with a

much smaller support radius.