Ck-B-splines with Square Support on a Three-Direction Mesh of the Plane

Numerical Algorithms 34: 67–84, 2003. 2003 Kluwer Academic Publishers. Printed in the Netherlands.

Ck-B-splines with square support ona three-direction mesh of the plane

A. Mazroui, D. Sbibih and A. TijiniDépartement de Mathématiques et Informatique, Faculté des Sciences,

Université Mohammed I, Oujda, MoroccoE-mail: {mazroui;sbibih;tijini}@sciences.univ-oujda.ac.ma

Received 17 September 2002; accepted 21 May 2003Communicated by P.J. Laurent

Let τ be the uniform triangulation generated by the usual three-directional mesh of theplane and let �1 be the unit square consisting of two triangles of τ . We study the space ofpiecewise polynomial functions in Ck(R2) with support �1 having a sufficiently high de-gree n, which are symmetrical with respect to the first diagonal of �1. Such splines are called�1-splines. We first compute the dimension of this space in function of n and k. Then, forany fixed k � 0, we prove the existence of �1-splines of class Ck and minimal degree. Thesesplines are not unique. Finally, we describe an algorithm computing the Bernstein–Béziercoefficients of these splines, and we give an example.

Keywords: B-splines, �1-splines, minimal degree

AMS subject classification: 41A05, 41A15, 65D05, 65D07

1. Introduction

Let τ be the uniform triangulation of R2, whose set of vertices is Z

2, and whoseedges are parallel to the three directions e1 = (1, 0), e2 = (0, 1) and e3 = (1, 1). LetPn be the space of bivariate polynomials of total degree at most n, and let P

kn(τ ) be the

space of piecewise polynomial functions of degree n and class Ck defined on τ .In general, the construction of low-degree B-splines with small support on uniform

meshes of the plane is not a very difficult task thanks to the fine properties of the localrepresentation of polynomial pieces in Bernstein–Bézier bases on triangles. Some ex-amples are described in [4] under the name of vertex-splines, and recently, another studyof this kind of B-splines is introduced in [1]. On the uniform 3-direction mesh, thereis a variety of possible shapes for small supports. B-splines with supports consistingof one, two or six triangles have been described in [7,8,11] by Mazroui et al. Startingfrom these B-splines, the authors have constructed new families of composed B-splinesby repeated convolution of one of the previous B-splines with the piecewise affine pyra-mid π0 whose support is the regular hexagon consisting of the six triangles surrounding

68 A. Mazroui et al. / B-splines with square support

the origin (see [9,12]). These B-splines have been used in [2,6,10] for solving someinterpolation and approximation problems.

The main purpose of the present paper is to study the dimension of the space ofsmooth piecewise polynomial functions having as support the square �1 consisting oftwo triangles of τ . For the sake of simplicity, we have assumed the symmetry of the�1-splines with respect to the first diagonal of the square �1, i.e., their B-coefficientsare the same on each triangle of �1. Otherwise, it would be more difficult to obtaingeneral results. For a smoothness order k, we give a construction of the corresponding�1-splines and we determine their minimal degree nk.

The �1-splines of minimal degree constitute building blocks for the constructionof new families of composed B-splines. For example, a composed B-spline φ can beobtained by repeated convolution of one �1-spline with π0. In this case, it is not hardeither to compute the smoothness and the degree of φ, or to determine the space P(φ)

of polynomials of maximal total degree included in the space S(φ) generated by theinteger translates of φ. This gives immediately the approximation order of a smoothfunction in S(φ). These properties and the construction of quasi-interpolants are directconsequences of the Strang–Fix theory applied to the Fourier transform of φ.

The paper is organized as follows. In section 2, we introduce the definitions andnotations and we give a series of preliminary results which are used for showing the mainresults of the paper. They consist in selecting a minimal set of B-coefficients from whichall the others can be deduced. This selection allows us to prove the main theorems givenin section 3. We show that for n < nk, there does not exist any �1-spline of degree nand class Ck. For n � nk, we give the dimension of the space of �1-splines of degree nand class Ck. In particular, for n = nk, this dimension is equal to [(k + 1)/2] + 1.In section 4, we give an interesting property of �1-splines of minimal degree. We showthat these �1-splines are symmetrical with respect to the second diagonal of �1. We alsodescribe an algorithm allowing to compute their B-coefficients. As an example, we giveexplicitly the construction of �1-splines of class C4 and minimal degree 14. Finally, insection 5 we present some concluding remarks.

2. Definitions, notations and preliminary results

Let T1 = A1A2A3 be a triangle of τ , then the barycentric coordinates λ=(λ1, λ2, λ3) of a point M ∈ R

2 with respect to T1 satisfy{λ1A1 + λ2A2 + λ3A3 = M,

λ1 + λ2 + λ3 = 1.

In the following, for a multi-index i = (i1, i2, i3) of N3, we denote as usual

|i| = i1 + i2 + i3, i! = i1!i2!i3!, λi = λi1λi2λi3 .

A. Mazroui et al. / B-splines with square support 69

Figure 1. B-coefficients of P1 and P2 for n = 4 (ai = a(i), bi = b(i), |i| = 4).

The(n+2

2

)Bernstein polynomials of total degree n defined by Bn

i (λ) = (n!/i!)λi for|i| = n, form a basis for the space Pn(T1). They satisfy∑

|i|=nBni (λ) = 1 for all λ and Bn

i (λ) � 0 for all λ ∈ T1.

Each polynomial P1 in Pn(T1) has a unique representation of the form:

P1(λ) =∑|i|=n

a(i)Bni (λ) for all λ ∈ T1.

Its coefficients {a(i): |i| = n} are the Bernstein–Bézier coefficients (in short:B-coefficients) of P1 on T1 and are associated with the

(n+2

2

)nodes {A(i) =

(1/n)∑3

j=1 ijAj , |i| = n} of T1, to form the set of control points {a(i) = (A(i), a(i)) ∈R

3, |i| = n} in R3, also called the B-net of P1 on T1. Therefore, the graph of P1 lies

in the convex hull of its B-net on T1 and the B-coefficients (a(i))|i|=n are identified withthe corresponding nodes (A(i))|i|=n (see figure 1).

If T2 = A1A2A4 is another triangle of τ adjacent to T1, then A4 = A1 + A2 − A3.Let µ = (µ1, µ2, µ3) be the barycentric coordinates of a point M ∈ R

2 with respectto T2 and let P2(λ) = ∑

|i|=n b(i)Bni (λ) be a polynomial in Pn(T2) (see figure 1).

We need the following result which is given in [3, corollary 5.1, p. 67].

Lemma 2.1. Let S be the piecewise polynomial function defined on T1 ∪ T2 by:

S|T1 = P1 and S|T2 = P2.

Then, for 0 � k � n, S is of class Ck on T1 ∪ T2 if and only if

b(r, s, t) =t∑

u=0

(−1)u(t

u

) t−u∑v=0

(t − u

v

)a(r + v, s + t − u, u)

for all 0 � t � k and r + s = n− t.


(a) (b)

Figure 2.

Definition 2.1. We call �1-spline any polynomial spline χ defined on R2 with sup-

port �1 and satisfying the following property:

χ is symmetrical with respect to the first diagonal of the support �1. (P)

For (n,m, k) ∈ N3, (x, y) ∈ R

2 and A a set, we denote

In = {(r, s, t) ∈ N

3 such that r + s + t = n}, I kn = {

(r, s, t) ∈ In such that t � k},

Pn(τ,�1) = {space of �1-splines whose restriction to each triangle of τ is

a polynomial of total degree � n},Pkn(τ,�1) = {

χ ∈ Pn(τ,�1) such that χ is of class Ck on R2},

Mm,n = space of real matrices of order m× n,

[x] = the floor of x, δx,y ={

1 for x = y,

0 otherwise,and

1{x∈A} ={

1 if x ∈ A,

0 otherwise,nk =

{3k + 2 if k is even,

3k + 3 if k is odd.

Let χ be a �1-spline of Pkn(τ,�1). It is clear that χ is completely determined by

its B-coefficients on the two triangles T1 and T2 of its support �1 (see figure 2(a)). Onthe other hand, property (P) implies that the B-coefficients of χ are the same on eachtriangle of �1. Then, in order to facilitate their computation on T1 (for example), wesubdivide it into subsets of B-coefficients as indicated in figure 2(b).

A= {a(r, s, t); (r, s, t) ∈ In and r � k or s � k

},

A1 ={a(r, s, t); (r, s, t) ∈ I kn , k < s and n−

[3k + 3

2

]< r

},

A2 ={a(r, s, t); (r, s, t) ∈ I kn , k < r and n−

[3k + 3

2

]< s

},


B1 ={a(r, s, t); (r, s, t) ∈ I kn , k < s and

[n

2

]+ 1 � r � n−

[3k + 3

2

]},

B2 ={a(r, s, t); (r, s, t) ∈ I kn and k < s � r �

[n

2

]},

B3 ={a(r, s, t); (r, s, t) ∈ I kn and k < r < s �

[n

2

]},

B4 ={a(r, s, t); (r, s, t) ∈ I kn , k < r and

[n

2

]+ 1 � s � n−

[3k + 3

2

]},

D= {a(r, s, t); (r, s, t) ∈ In and k < min(r, s, t)

}.

Using the Ck smoothness conditions of χ across the edges A1A3 and A2A3, weeasily show the following result.

Proposition 2.1. The B-coefficients of χ in the subset A are all equal to zero.

According to lemma 2.1, the Ck smoothness conditions of χ across the edge A1A2

are equivalent to

a(r, s, t) =t∑

u=0

(−1)u(t

u

) t−u∑v=0

(t − u

v

)a(r + v, s + t − u− v, u)

for all (r, s, t) ∈ I kn . (1)

Thus, equations (1) will allow us to identify the B-coefficients belonging to the setsA1, A2, B1, B2, B3 and B4. We first give a result in which we prove that equations (1)are equivalent to similar equations with sets of indices (r, s, t) smaller than I kn . For this,we need the following notations:

J kn =

{(r, s, t) ∈ I k+1

n , t is even, t �= 0, r �= s, r �= s − 1 and

max(r, s) � n−[

3k + 3

2

]}, (2)

g(r, s, t)=(

t∑u=0

(−1)u(t

u

) t−u∑v=0

(t − u

v

)a(r + v, s + t − u− v, u)

)− a(r, s, t).

Remark 2.1. It is clear that equations (1) can be written as follows:

g(r, s, t) = 0 for all (r, s, t) ∈ I kn .

Moreover, if t is even we have

g(r, s, t) =t−1∑u=0

(−1)u(t

u

) t−u∑v=0

(t − u

v

)a(r + v, s + t − u− v, u). (3)


Proposition 2.2. Equations (1) are equivalent to

(i) g(r, s, t) = 0 for all (r, s, t) ∈ J kn .

(ii) The B-coefficients of the subsets A1 and A2 are all equal to zero.(4)

Proof. It is similar to that of [7, proposition 3.9]. �

In order to compute the remaining B-coefficients belonging to the set B =(B1 ∪ B2 ∪ B3 ∪ B4), we consider the rth row Sr formed by the B-coefficients of(B1 ∪B2) and parallel to the edge A2A3, and the sth row Ts formed by the B-coefficientsof (B3 ∪ B4) and parallel to the edge A1A3. More specifically, for r, s ∈ {[n/2]+1; . . . ;n− [(3k + 3)/2]} we have

Sr = {a(r, n − r − u, u) ∈ B; u � k and u � n− k − r − 1

},

Ts = {a(n − s − u, s, u) ∈ B; u � k and u � n− k − s − 1

},

and for

r ∈{[

n− k + 1

2

]; . . . ;

[n

2

]}and s ∈

{[n− k

2

]+ 1; . . . ;

[n

2

]}we have

Sr = {a(r, n − r − u, u) ∈ B; u � k and n− 2r � u � n− k − r − 1

},

Ts = {a(n− s − u, s, u) ∈ B; u � k and n− 2s < u � n− k − s − 1

}.

According to the definitions of (Bi)1�i�4, it is easy to verify that

B1 =n−[(3k+3)/2]⋃r=[n/2]+1

Sr, B2 =[n/2]⋃

r=[(n−k+1)/2]Sr,

B3 =[n/2]⋃

s=[(n−k)/2]+1

Ts, B4 =n−[(3k+3)/2]⋃s=[n/2]+1

Ts.

Proposition 2.3. (1) If n < nk, then the elements of B2 ∪ B3 are all equal to zero.(2) If n � nk, then

(i) for r ∈ {[(n− k + 1)/2]; . . . ; [n/2]}, the elements of Sr are solutions of a linearsystem with a matrix of rank (r + [(k + 1)/2] − [n/2]), and the right-hand sidedepends only on elements of {Sr ′ ∪ Tr ′ ; r + 1 � r ′ � n− [(3k + 3)/2]}.

(ii) for s ∈ {[(n− k)/2] + 1; . . . ; [n/2]}, the elements of Ts are solutions of a linearsystem with a matrix of rank (s + [(k + 1)/2] − [(n+ 1)/2]), and the right-handside depends only on elements of {Ss ′ ∪ Ts ′ ; s + 1 � s′ � n− [(3k + 3)/2]}.

Proof. We first prove (2).


(i) Let r ∈ {[(n− k + 1)/2]; . . . ; [n/2]} and mr = min(k, n − k − r − 1). Fromthe definition of Sr we have

a(r, n − r − u, u) ∈ Sr ⇔ n− 2r � u � mr.

On the other hand, by using (4)(i), we deduce that the elements of Sr satisfy the follow-ing equations

t−1∑u=0

(−1)u(t

u

) t−u∑v=0

(t − u

v

)a(r + v, n− r − u− v, u) = 0,

for all (n, n− r − t, t) ∈ J kn ,

which are equivalent to

t−1∑u=n−2r

(−1)u(t

u

)a(r, n − r − u, u)

= −t−1∑u=0

(−1)u(t

u

) t−u∑v=1

(t − u

v

)a(r + v, n− r − u− v, u)

−n−2r−1∑u=0

(−1)u(t

u

)a(r, n − r − u, u)

for all t even and n− 2r + 1 � t � k + 1. (5)

Let us denote by b(r, t) the right-hand side of (5). When t − 1 > mr , (5) becomes

mr∑u=n−2r

(−1)u(t

u

)a(r, n − r − u, u) = b(r, t) −

t−1∑u=mr+1

(−1)u(t

u

)a(r, n − r − u, u).

Since a(r, n − r − u, u) ∈ A for all u � mr + 1, we deduce from proposition 2.1 thatthe latter equations become

mr∑u=n−2r

(−1)u(t

u

)a(r, n − r − u, u) = b(r, t). (6)

Finally, if we put

θr = card{t; (r, n− r − t, t) ∈ J k

n

} = r +[k + 1

2

]−[n

2

]and γr = card Sr = mr − (n − 2r) + 1, then from (5) and (6), the elements of Srare solutions of a linear system whose matrix Mr is in Mθr ,γr . Since n � nk and[(n− k + 1)/2] � r � [n/2], we have θr � γr . On the other hand, the first θr columnsof Mr form the nonsingular matrix Aθr,n−2r+2 (respectively −Bθr−1,n−2r+1) if n is even(respectively if n is odd), where the matrices Aθr ,n−2r+2 and Bθr−1,n−2r+1 are defined in[7, lemma 6.3].


(ii) As in (i), we show for s ∈ {[(n− k)/2] + 1, . . . , [n/2]} that the elements of Tsare solutions of the following systems:

t−1∑u=n−2s+1

(−1)u(t

u

)a(n − s − u, s, u) = c(s, t) for all t even and

n− 2s + 1 � t � ms + 1,

ms∑u=n−2s+1

(−1)u(t

u

)a(n − s − u, s, u) = c(s, t) for all t even and

ms + 1 < t � k + 1,

(7)

where

c(s, t)= −n−2s∑u=0

(−1)u(t

u

)a(n− s − u, s, u)

−t−1∑u=0

(−1)u(t

u

) t−u∑v=1

(t − u

v

)a(n− s − u− v, s + v, u).

The rest of the proof of (ii) is similar to that of (i).For the proof of (1), it suffices to prove that the elements of B2 are all equal to zero.

For B3, the same technique can be used. First, remark from the definition of Sr and theinequality n < nk that Sr = ∅ if [(n− k)/2] + 1 � r � k + 1, so B1 = ⋃[n/2]

r=k+2 Sr .We will prove by induction on r that the elements of Sr are all equal to zero. Indeed,

for r = [n/2], and as n < nk, we verify that [n/2] > n − [(3k + 3)/2]. ThereforeSr ⊂ A ∪ A1 = {0}. Now, we assume that for some r satisfying k + 2 � r < [n/2],all the elements of Sj , r + 1 � j � [n/2], are equal to zero. According to (5) and (6),the elements of Sr are solutions of a linear system whose matrix Mr is in Mθr ,γr . Sincen < nk and [(n− k + 1)/2] � r � [n/2], we have θr � γr . The first γr lines of Mr formthe nonsingular matrix Aβr ,n−2r+2 (respectively −Bβr−1,n−2r+1) if n is even (respectivelyif n is odd), where the matricesAβr ,n−2r+2 andBβr−1,n−2r+1 are defined in [7, lemma 6.3].From the induction hypothesis, the right-hand side br = (br,t )t∈2N,n−2r+1�t�k+1 is equalto zero, so the elements of Sr are all equal to zero. �

Proposition 2.4. (1) If n � nk, then B1 = B4 = ∅.(2) If n > nk, then for r, s ∈ {[n/2] + 1; . . . ;n− [(3k + 3)/2]} we have:

(i) The elements of Sr are solutions of a linear system with a matrix of rank [(k + 1)/2],and with the right-hand side depends only on the elements of {Sr ′; r + 1 � r ′ �n− [(3k + 3)/2]}.

(ii) The elements of Ts are solutions of a linear system with a matrix of rank [(k + 1)/2],and with the right-hand side depends only on the elements of {Ts ′ ; s + 1 � s′ �n− [(3k + 3)/2]}.

Proof. (1) It results from the inequality n � nk and the definitions of B1 and B4.(2) The proof is similar to that of proposition 2.3. �


3. Main results

In this section we give the main results of the paper.

Theorem 3.1. For (n, k) ∈ N2 such that n < nk, there is no nonzero �1-spline of

class Ck and degree n.

Proof. Let χ be an element of Pkn(τ,�1). As n < nk, we easily verify that D = ∅.

Then, from propositions 2.1–2.4, we deduce that all the B-coefficients of χ are equal tozero. �

Theorem 3.2. For (n, k) ∈ N2 such that n � nk, there exist (Un,k + Vn,k) linearly

independent �1-splines of class Ck and degree n, whereUn,k = 2

([k

2

]+ 1

)([n+ 1

2

]−[

3k + 3

2

])+([

k

2

]+ 1

)1{n∈2N},

Vn,k = (n− 3k − 2)(n− 3k − 1)

2.

Proof. Let χ be a nonzero element of Pkn(τ,�1). The dimension of P

kn(τ,�1) is equal

to the minimal number of B-coefficients of χ which are necessary to compute all theother ones.

Recall from propositions 2.1 and 2.2 that χ is completely determined by itsB-coefficients in the sets (Bi)1�i�4 and D.

Using propositions 2.3 and 2.4, the minimal number of B-coefficients necessary tocompute all the elements of (B1 ∪ B2 ∪ B3 ∪ B4) is equal to Un,k, where

Un,k =[n/2]∑

r=[(n−k+1)/2]

(card(Sr)−

(r +

[k + 1

2

]−[n

2

]))

+[n/2]∑

s=[(n−k)/2]+1

(card(Ts)−

(s +

[k + 1

2

]−[n+ 1

2

]))

+n−[(3k+3)/2]∑r=[n/2]+1

(card(Sr)−

[k + 1

2

])+

n−[(3k+3)/2]∑s=[n/2]+1

(card(Ts)−

[k + 1

2

])

=[n/2]∑

r=[(n−k+1)/2]

(min(k, n− k − r − 1) − (n− 2r) + 1 −

(r +

[k + 1

2

]−[n

2

]))

+[n/2]∑

s=[(n−k)/2]+1

(min(k, n− k − s − 1) − (n− 2s)

−(s +

[k + 1

2

]−[n+ 1

2

]))


+n−[(3k+3)/2]∑r=[n/2]+1

(min(k, n− k − r − 1) + 1 −

[k + 1

2

])

+n−[(3k+3)/2]∑s=[n/2]+1

(min(k, n− k − s − 1) + 1 −

[k + 1

2

]).

By straightforward but tedious computation we get

Un,k = 2

([k

2

]+ 1

)([n+ 1

2

]−[

3k + 3

2

])+([

k

2

]+ 1

)1{n∈2N}.

On the other hand, by using the definition of D, we easily verify that

Vn,k = card D = (n− 3k − 2)(n− 3k − 1)

2.

Therefore, dim(Pkn(τ,�1)) = Un,k + Vn,k. �

Theorem 3.3. For k ∈ N, there exist ([(k + 1)/2] + 1) linearly independent �1-splinesof class Ck and minimal degree nk.

Proof. It is clear that nk satisfies the equality [(nk + 1)/2] = [(3k + 3)/2]. Then, if wetake n = nk in theorem 3.2, we obtain Unk,k = [k/2]+ 1 and Vnk,k = 1{k/∈2N}. Therefore,

dim(Pknk(τ,�1)

) =[k

2

]+ 1 + 1{k/∈2N} =

[k + 1

2

]+ 1. �

4. �1-splines of minimal degree

In this section, we are interested in the construction of a basis of �1-splines ofclass Ck, k ∈ N, and minimal degree nk. In this case, the sets B1 and B4 are empty and

D =

a(nk

3,nk

3,nk

3

)if k is odd,

∅ if k is even.

We first give an interesting property of �1-splines of minimal degree.

Theorem 4.1. If χk is a �1-spline of class Ck and minimal degree nk, k ∈ N, then itsB-coefficients a(r, s, t) in the triangle A1A2A3 are symmetrical with respect to the sec-ond diagonal A3A4 (see figure 2(a)), i.e.,

a(r, s, t) = a(s, r, t) ∀(r, s, t) ∈ Ink .

Proof. We will do the proof for k even, i.e., k = 2p, thus nk = 6p+ 2. The case k oddis similar.


According to the preceding results we have B1 = B4 = D = ∅. Moreover, frompropositions 2.1, 2.2 and the definitions of B2 and B3, it suffices to prove that

a(r, s, t) = a(s, r, t) for all (r, s, t) ∈ B2. (8)

On the other hand, we have(a(r, s, t) ∈ B2 and r �= s

) ⇔ (a(s, r, t) ∈ B3

),

B2 =3p+1⋃

r=2p+1

Sr, B3 =3p+1⋃

s=2p+2

Ts,

and for r, s ∈ {2p + 2, . . . , 3p + 1}{a(r, 6p + 2 − r − u, u) ∈ Sr ⇔ 6p + 2 − 2r � u � 4p + 1 − r,

a(6p + 2 − s − u, s, u) ∈ Ts ⇔ 6p + 2 − 2s < u � 4p + 1 − s.

Therefore, in order to prove (8), it suffices to show by induction on r that the elementsof Tr are equal to those of S∗

r defined by S∗r = {a(r, 6p + 2 − r − u, u); 6p + 2 − 2r <

u � 4p + 1 − r}. From (5) and (6), the elements of S∗r for r = 3p + 1 are solutions of

the following equations:

t−1∑u=0

(−1)u(t

u

)a(3p + 1, 3p + 1 − u, u)

= −t−1∑u=0

(−1)u(t

u

) t−u∑v=1

(t − u

v

)a(3p + 1 + v, 3p + 1 − u− v, u)

for all t even and 1 � t � p + 1 andp∑u=0

(−1)u(t

u

)a(3p + 1, 3p + 1 − u, u)

= −t−1∑u=0

(−1)u(t

u

) t−u∑v=1

(t − u

v

)a(3p + 1 + v, 3p + 1 − u− v, u)

for all t even and p + 2 � t � 2p.

Since a(3p + 1 + v, 3p + 1 − u− v, u) ∈ A ∪ A1 for all t even, 1 � t � 2p, 0 � u �t − 1 and 1 � v � t − u, we deduce from propositions 2.1, 2.2 that the last equationsbecome

t−1∑u=1

(−1)u(t

u

)a(3p + 1, 3p + 1 − u, u)

= −a(3p + 1, 3p + 1, 0) for all t even and 1 � t � p + 1,(9)


p∑u=1

(−1)u(t

u

)a(3p + 1, 3p + 1 − u, u)

= −a(3p + 1, 3p + 1, 0) for all t even and p + 2 � t � 2p.

On the other hand, from (7), the elements of T3p+1 are solutions of the following equa-tions

t−1∑u=1

(−1)u(t

u

)a(3p + 1 − u, 3p + 1, u)

= −a(3p + 1, 3p + 1, 0) for all t even and 1 � t � p + 1,p∑

u=1

(−1)u(t

u

)a(3p + 1 − u, 3p + 1, u)

= −a(3p + 1, 3p + 1, 0) for all t even and p + 2 � t � 2p.

(10)

We remark from (9) and (10) that the elements of the sets S∗3p+1 and T3p+1 are solutions

of the same linear system with the same right-hand side. Since the matrix Bp−1,2 of thissystem, defined in [7, lemma 6.3], is nonsingular, we deduce that

a(3p + 1 − u, 3p + 1, u) = a(3p + 1, 3p + 1 − u, u) for all 1 � u � p.

Now, for r > 2p + 1 we assume that

a(r∗, 6p + 2 − r∗ − u, u) = a(6p + 2 − r∗ − u, r∗, u)for all r � r∗ � 3p + 1 and a(r∗, 6p + 2 − r∗ − u, u) ∈ B2.

From (5) and (6), the elements of S∗r+1 are solutions of the following equations:

t−1∑u=6p−2r+3

(−1)u(t

u

)a(r + 1, 6p + 1 − r − u, u)

= −6p−2r∑u=0

(−1)u(t

u

)a(r + 1, 6p + 1 − r − u, u)

−t−1∑u=0

(−1)u(t

u

) t−u∑v=1

(t − u

v

)a(r + 1 + v, 6p + 1 − r − u− v, u)

for all t even and 6p + 3 − 2r � t � 4p + 2 − r, and(11)

4p+1−r∑u=6p−2r+3

(−1)u(t

u

)a(r + 1, 6p + 1 − r − u, u)

= −6p−2r∑u=0

(−1)u(t

u

)a(r + 1, 6p + 1 − r − u, u)


−t−1∑u=0

(−1)u(t

u

) t−u∑v=1

(t − u

v

)a(r + 1 + v, 6p + 1 − r − u− v, u)

for all t even and 4p + 3 − r � t � 2p,

and from (7), the elements of Tr+1 are solutions of the following equations

t−1∑u=6p−2r+3

(−1)u(t

u

)a(6p + 1 − r − u, r + 1, u)

= −6p−2r∑u=0

(−1)u(t

u

)a(6p + 1 − r − u, r + 1, u)

−t−1∑u=0

(−1)u(t

u

) t−u∑v=1

(t − u

v

)a(6p + 1 − r − u− v, r + 1 + v, u)

for all t even and 6p + 3 − 2r � t � 4p + 2 − r, and4p+1−r∑

u=6p−2r+3

(−1)u(t

u

)a(6p + 1 − r − u, r + 1, u)

= −6p−2r∑u=0

(−1)u(t

u

)a(6p + 1 − r − u, r + 1, u)

−t−1∑u=0

(−1)u(t

u

) t−u∑v=1

(t − u

v

)a(6p + 1 − r − u− v, r + 1 + v, u)

for all t even and 4p + 3 − r � t � 2p.

(12)

Using the induction hypothesis, the right-hand sides of the two linear systems definedrespectively by (11) and (12) are equal. Moreover, since the matrices of these two sys-tems coincide with the nonsingular matrix Br−2p−2,6p−2r+4 defined in [7, lemma 6.3],we deduce that the elements of S∗

r+1 are equal to those of Tr+1. �

4.1. Computational algorithm

We will do the computations for k even, i.e., k = 2p, thus nk = 6p + 2. The casek odd can be treated in the same way.

As the sets B1, B4 and D are empty, the figure 2(b) takes the form shown in figure 3.From propositions 2.1, 2.2, the B-coefficients belonging to (A ∪ A1 ∪ A2) are all equalto zero. On the other hand, from theorem 4.1, the B-coefficients of B3 can be computedfrom those of B2. Moreover, as dim P

2p6p+2(τ,�1) = p + 1, all the B-coefficients in

B2 = ⋃3p+1r=2p+1 Sr can be computed only in terms of (p + 1) ones. More precisely, as

indicated in the proof of proposition 2.3, the elements of each Sr, 2p+1 � r � 3p+1,are expressed in function of a(r, r, 6p + 2 − 2r) and the B-coefficients of

⋃3p+1r ′=r+1 Sr ′ .


Figure 3.

It is easy to see that from the definitions of B2 and B3, these sets can be written asfollows

B2 = {a(r, s, t); t � 2p and 2p + 1 � s � r � 3p + 1

},

= {a(3p + 1 − u, 3p + 1 − v, u+ v); 0 � u � v � p

},

B3 = {a(r, s, t); t � 2p and 2p + 1 � r < s � 3p + 1

},

= {a(3p + 1 − u, 3p + 1 − v, u+ v); 0 � v < u � p

}.

If we put for 0 � u, v � p

xu,v = a(3p + 1 − u, 3p + 1 − v, u+ v),

Lp =B2 ∪ B3 = {xu,v; 0 � u, v � p},then, from theorem 4.1 we have

xu,v = xv,u for all 0 � u, v � p. (13)

The computation of the elements of Lp can be done row by row. Indeed, we assume thatthe elements {xu,v; 0 � u � l − 1, 0 � v � p} of the first l rows of Lp are known,then from (13), we deduce the elements {xl,v; 0 � v � l − 1}. In order to computethe remaining elements {xl,v; l � v � p} of the row l of Lp, we need the followingnotations:

�xl = (xl,v)l<v�p, �dl = (dl,h)l<h�p, where

dl,h = −l∑

w=0

(−1)w+l(

2h

w + l

)xl,w

−min(2h,p+l)−1∑

u=0

(−1)u(

2h

u

) min(u,l−1)∑w=max(0,l+u−2h,u−p)

(2h− u

l − w

)xw,u−w,

with the convention∑s

i=r = 0, if r > s.

Theorem 4.2. For l ∈ {0, . . . , p − 1}, the vector �xl is solution of the linear system

Bp−l−1,2l+2 �xl = �dl,


where the matrix Bp−l−1,2l+2 = (Bp−l−1,2l+2(u, v))0�u,v�p−l−1, with

Bp−l−1,2l+2(u, v) =(−1)v+1

(2l + 2 + 2u

2l + 1 + v

)if 0 � v � 2u,

0 otherwise.

Proof. Let r ∈ {2p + 2, . . . , 3p + 1} and put l = 3p + 1 − r, then l ∈ {0, . . . ,p − 1}. From (5) and (6), the elements of S∗

r = (a(r, 6p + 2 − r, u))6p+2−2r<u�4p+1−rare solutions of the linear system

Br−2p−2,6p+4−2rS∗r = �cr ,

where �cr = (cr,h)3p+2−r�h�p with cr,h = br,2h+( 2h

6p+2−2r

)a(r, r, 6p+2−2r). Since S∗

r =(a(r, 6p+2−r, u))6p+2−2r<u�4p+1−r = (xl,v)l<v�p and Br−2p−2,6p+4−2r = Bp−l−1,2l+2,it suffices for proving theorem 4.2, to verify that �cr = �dl . Indeed,

cr,h = −6p+2−2r∑u=0

(−1)u(

2h

u

)a(r, 6p + 2 − r − u, u)

−2h−1∑u=0

(−1)u(

2h

u

) 2h−u∑v=1

(2h − u

v

)a(r + v, 6p + 2 − r − u− v, u)

= −2l∑u=0

(−1)u(

2h

u

)a(3p + 1 − l, 3p + 1 + l − u, u)

−2h−1∑u=0

(−1)u(

2h

u

) 2h−u∑v=1

(2h − u

v

)a(3p + 1 − l + v, 3p + 1 + l − u− v, u).

Since, (a(3p + 1 − w, 3p + 1 − q, q + w) ∈ B2 ∪ B3

) ⇔ 0 � w, q � p,

we have(a(3p + 1 − w, 3p + 1 − q, q + w) = 0

) ⇔ max(w, q) > p or min(w, q) < 0.

Therefore,

cr,h = −2l∑u=l

(−1)u(

2h

u

)a(3p + 1 − l, 3p + 1 + l − u, u)

−2h−1∑u=0

(−1)u(

2h

u

) min(2h−u,l,l+p−u)∑v=max(1,l−u)

(2h− u

v

)× a(3p + 1 − l + v, 3p + 1 + l − u− v, u)


= −2l∑u=l

(−1)u(

2h

u

)xl,u−l −

2h−1∑u=0

(−1)u(

2h

u

)min(2h−u,l,l+p−u)∑v=max(1,l−u)

(2h − u

v

)xl−v,u+v−l

= −l∑

w=0

(−1)w+l(

2h

w + l

)xl,w

−min(2h,p+l)−1∑

u=0

(−1)u(

2h

u

) min(u,l−1)∑w=max(0,l+u−2h,u−p)

(2h− u

l − w

)xw,u−w

= dl,h. �

4.2. Example: a basis of the space P414(τ,�1)

We will use the above algorithm for determining a basis of the space Pknk(τ,�1)

when k = 4. In this case p = 2 and n4 = 14.The vector �x0 = (x01, x02)

T is the solution of the linear system B1,2 �x0 = �d0, where

B1,2 =(−2 0

−4 6

)and �d0 =

(−x00

−x00

), so �x0 = 1

6

(3x00

x00

).

In the same way, the vector �x1 = (x12) is the solution of the linear system B0,4 �x1 = �d1,where B0,4 = (−4) and �d1 = (2x00 − 6x11), so x12 = (−x00 + 3x11)/2.

If we put x00 = 6α, x11 = 2β, x22 = γ and θ = 3(β − α) then the B-coefficientsof a �1-spline χ of class C4 and minimal degree 14 are given in figure 4.

If we choose (α, β, γ ) equal respectively to (1, 0, 0), (0, 1, 0) and (0, 0, 1), weobtain three linearly independent �1-splines of minimal degree in the space P

414(�, τ).

Their B-coefficients and corresponding graphs are given in figure 5.

Figure 4.


Figure 5.

5. Remarks

Remark 5.1. As mentioned in the introduction, the �1-splines of minimal degree areuseful for the construction of other families of B-splines. Indeed, if we denote by χka �1-spline of class Ck and minimal degree nk, then a composed B-spline χr

k , r ∈ N,is defined by χr

k = χk 7 πr0 , where πr

0 = π0 7 · · · 7 π0 (r times) is the box-spline inP

2r3r+1(τ ) (see, e.g., [5, chapter 1], or [3, chapter 2]). As a consequence of the convolu-

tion, we easily verify that χrk is of class Ck+2r and degree 3(r + k) + 2 for k even and

degree 3(r + k + 1) for k odd. Moreover, its support is the hexagon �r+1 with vertices{(r + 1, 0); (r + 1, r + 1); (0, r + 1); (−r, 1); (−r,−r); (1,−r)}.

Remark 5.2. For k = −1, we can define χ−1 as the characteristic function of thesquare �1. In this case, χr

−1, r ∈ N, is a box-spline of class C2r−1 and degree 3r.Thus, the B-splines χr

k are a natural extension of the classical box-splines. Unfortu-nately, for k � 0, χr

k does not satisfy a refinement equation, therefore there is no subdi-vision algorithm. However, once the B-coefficients of χk are known, those of χr

k can becomputed by standard convolution algorithms (see [9]). When comparing the composedB-splines χr

k with classical box-splines of P2r−13r (τ ), we observe that, for a given smooth-

ness, we get a smaller support, but of course a higher degree. Therefore, the computationof interpolants or quasi-interpolants based on χr

k becomes easier (sparse matrices).

Remark 5.3. The composed B-splines χrk are potential good candidates, as classical box-

splines, for the approximation by interpolation (as, e.g., in [6], for r = 1) or by quasi-


interpolation. Using the Strang–Fix theory [13] connecting the zeros of derivatives of theFourier transform of χr

k on the mesh (2πZ)2 to the maximal space P(χrk ) of polynomials

included in S(χrk ), we deduce that P(χr

k ) = P2r−1. Therefore, the approximation orderof a smooth function in the space S(χr

k ) is exactly 2r. Quasi-interpolants which carryout this order can be written in the form

Q(f ) =∑α∈Z2

µα(f )χrk (· − α),

where µα(f ) is a linear form that can be a finite combination of discrete values f (β)or mean values

∫f (x)χr

k (x − β) dx for β ∈ Z2 situated in a bounded neighbourhood

of α. There exist various methods in the literature which allow us the construction ofsuch quasi-interpolants.

References

[1] P. Alfeld and L.L. Schumaker, Non-existence of star-supported spline bases, SIAM J. Math. Anal. 31(2000) 1482–1501.

[2] El. Ameur and D. Sbibih, Cardinal interpolation by H-splines on a three-directional mesh of the plane,submitted.

[3] C.K. Chui, Multivariate Splines, CBMS–NSF Regional Conference Series in Applied Mathematics,Vol. 54 (SIAM, Philadelphia, PA, 1988).

[4] C.K. Chui, Vertex Splines and their applications to interpolation of discrete data, in: Computation ofCurves and Surfaces, eds. W. Dahmen et al. (Kluwer, Dordrecht, 1990) pp. 137–181.

[5] C. de Boor, K. Höllig and S. Riemenschneider, Box-Splines, Applied Mathematical Sciences, Vol. 98(Springer, New York, 1993).

[6] X. Guillet, Interpolation by new families of B-splines on uniform meshes of the plane, in: SurfaceFitting and Multiresolution Methods, eds. A. Le Méhauté, C. Rabut and L.L. Schumaker (VanderbiltUniv. Press, Nashville/London, 1997) pp. 183–190.

[7] A. Mazroui, P. Sablonnière and D. Sbibih, Existence and construction of H1-splines of class Ck on athree-direction mesh, Adv. Comput. Math. 17 (2002) 167–198.

[8] A. Mazroui and S. Sbibih, Existence and construction of ;1-splines of class Ck on a three-directionalmesh, Numer. Algorithms 26 (2001) 21–48.

[9] A. Mazroui and D. Sbibih, Algorithms for B-nets of some B-splines with hexagonal support on athree-directional mesh, submitted.

[10] P. Sablonnière, Quasi-interpolants associated with H-splines on a three-direction mesh, J. Comput.Appl. Math. 66 (1996) 433–442.

[11] P. Sablonnière, New families of B-splines on uniform mesh of the plane, in: CRM Proceedings andLecture Notes, Vol. 18, Centre de Recherche Mathématique de Montréal (1999) pp. 89–100.

[12] P. Sablonnière and D. Sbibih, Some families of splines with hexagonal support on a three-directionmesh, in: Mathematical Methods for Curves and Surfaces, eds. M. Daehlen, T. Lyche and L.L. Schu-maker (Vanderbilt Univ. Press, Nashville, 1995) pp. 467–475.

[13] G. Strang and G. Fix, A Fourier analysis of the finite element variational method, in: ConstructiveAspects of Functional Analysis, ed. G. Geymonat (CIME II Ciclo, 1971) pp. 793–840.

Documents

Ck-B-splines with Square Support on a Three-Direction Mesh of the Plane