mx ¤ ± j ±k g y (•(y)) ¤ Mx ,

(•(y)), (17.7)

‚v j ‚vk

j,k=1

holds for all y ∈ • ’1 (B(0, 3r )), ± ∈ S n’1 .

320 Interpolation on spheres and other manifolds

Now suppose that y, z ∈ U are given and that γ : [a, b] ’ M is a connecting piecewise

differentiable curve. We are going to bound its length from below.

For the moment, we will suppose that γ stays completely within the set • ’1 (B(0, 3r )).

Then v := • —¦ γ denotes a piecewise differentiable curve that connects •(y) with •(z) and

is completely contained in B(0, 3r ). Moreover, γ = • ’1 —¦ v gives

dv j ‚• ’1

n

dγ

= —¦ v,

dt ‚v j

dt j=1

so that

‚• ’1 ‚• ’1

n

dv j dvk

dγ dγ

, =

gγ (t) gγ (t) (v(t)), (v(t))

‚v j ‚vk

dt dt dt dt

j,k=1

dv

≥ mx .

dt 2

But this means in particular that

b

dv

L(γ ) ≥ m x ≥ m x b ’ a 2,

dt

a 2

where the last inequality follows from the fact that the shortest curve between two points

in Rn is the connecting line segment.

If γ leaves • ’1 (B(0, 3r )) then there exists a point z = • ’1 (c), c 2 = 3r , on the curve.

But since •(y) and •(z) are contained in the ball around zero with radius r , the computations

just made show that

L(γ ) ≥ L(γ ; a, c) ≥ m x c ’ a ≥ 2r m x ≥ m x b ’ a 2 .

2

Since γ is an arbitrary curve, we have proven that

dist(y, z) ≥ m x •(y) ’ •(z) 2 .

For the upper bound, we can choose an arbitrary curve that connects y and z, for exam-

ple, γ (t) = • ’1 (t•(y) + (1 ’ t)•(z)), t ∈ [0, 1]. Since this particular curve is everywhere

contained within • ’1 (B(0, 3r )), we can conclude from (17.7) that

dist(y, z) ¤ L(γ ) ¤ Mx •(y) ’ •(z) 2 .

The preceding result makes it easy to reduce the error estimates to those of the Rd case.

As usual, we give the error estimates for functions from the native space N (M) and express

them in terms of the ¬ll distance h X,M , which is now de¬ned using the geodesic distance

dist(·, ·). In the proof, we will also use the ¬ll distance for sets in Rn , which will be de¬ned

using the Euclidean norm. The reader should notice where each de¬nition is employed.

17.5 Notes and comments 321

∈

Theorem 17.21 Let M be a compact C Riemannian manifold. Suppose that

C (M — M) is positive de¬nite and we have ≥ 2k. Then there exist h 0 > 0 and C > 0

2k

such that for all f ∈ N (M) and all X ⊆ M with h X ¤ h 0 the error between f and its

interpolant s f,X can be bounded by

| f (x) ’ s f,X (x)| ¤ Ch k N (M) , x ∈ M.

X,M f

Proof For every x ∈ M we choose a chart (Ux , •x ) according to Lemma 17.20. Since M is

compact we need only a ¬nite number of them to cover M, say (U y j , • y j )1¤ j¤L . Let (U, •) be

one of these. By Proposition 17.18, the kernel (u, v) := (• ’1 (u), • ’1 (v)), u, v ∈ V :=

•(U ), is positive de¬nite on V . Moreover, because of the smoothness assumptions, we have

∈ C 2k (V — V ). As in Lemma 16.14, one sees that the power functions are related by

=P x ∈ U,

P ,X ©U (x) ,•(X ©U ) (•(x)),

and we can study the power function on the right-hand side, which now exists on an open

ball in Rn . Hence, Theorem 11.13 and Lemma 17.20 give

¤ CC (•(x))1/2 h k ©U ),•(U )

P ,•(X ©U ) (•(x)) •(X

¤ CC (•(x))1/2 h k ©U,U .

X

The number C (•(x)) can be uniformly bounded since • ’1 is in C up to the boundary of

•(U ). Moreover, h X ©U,U can be bounded by a constant times h X,M for suf¬ciently small

h X,M . Since we have only a ¬nite number of such charts, this completes the proof.

17.5 Notes and comments

Schoenberg [174] was the ¬rst to study positive semi-de¬nite, and in particular zonal, func-

tions on the sphere. Almost every other paper concerned with this subject is based on his

work. Since Schoenberg was interested in positive semi-de¬nite rather than positive de¬nite

functions, this has left plenty of room for other authors. Interestingly, besides the confusion

already mentioned about the term positive de¬niteness, in the context of the sphere there are

two different de¬nitions of positive de¬nite functions on the market. While some authors

de¬ne this as we have done, others, for example Narcowich [141], use an integral characteri-

zation. The latter approach is more restrictive than ours, as pointed out by Ron and Sun [157].

The ¬rst papers concerned with conditions for positive de¬niteness were by Light and

Cheney [106] and by Xu and Cheney [205]. In the ¬rst paper, the authors restricted them-

selves to the unit sphere in R2 or, in other words, to periodic basis functions. In these two

papers, positive de¬niteness for a ¬nite number N of centers was ¬rst considered: rather

than formulating conditions on that give rise to positive de¬nite interpolation matrices

for all N , the authors were looking for conditions only for a ¬xed N . Most of the subsequent

papers followed this approach. Besides the authors already mentioned, Menegatto has done

most of the investigations on positive de¬niteness; see for example [127, 128].

322 Interpolation on spheres and other manifolds

There are in the main three different approaches for providing error estimates for interpo-

lation by positive de¬nite functions on the sphere. The ¬rst, which we presented in Section

17.3, is due to Jetter et al. [89] with recent improvements by Morton and Neamtu [138].

The second mimics the Rd ideas of a local polynomial reproduction; details can be found in

the paper [72] by Golitschek and Light. Finally, the third approach is the one that works for

arbitrary smooth Riemannian manifolds. The idea of using local coordinates was employed

for radial basis functions by Levesley and Ragozin [103], even if their arguments differ

slightly from ours. The present author [197] has used the local coordinate argument in the

case of moving least squares approximation on the sphere.

A thorough general discussion of positive de¬nite functions on arbitrary manifolds started

with the paper [141] by Narcowich, that has been mentioned already.

Recent overviews of other approximation methods on the sphere were given by Freden

et al. in [65, 66] and by Fasshauer and Schumaker in [57].

References

[1] E. J. Akutowicz. On extrapolating a positive de¬nite function from a ¬nite interval.

Math. Scand., 7: 157“169, 1959.

[2] N. Aronszajn. Theory of reproducing kernels. Trans. Am. Math. Soc., 68: 337“404,

1950.

[3] S. Arya and D. M. Mount. Approximate nearest neighbor searching. In Proc. 4th

Ann. ACM-SIAM Symposium on Discrete Algorithms, pp. 271“280, New York,

ACM Press, 1993.