# 2. The Bernstein frame

N/A
N/A
Protected

Share "2. The Bernstein frame"

Copied!
20
0
0

Full text

(1)

10 December 2013

## Multivariate Bernstein operators and redundant systems

### Tan Duc Do and Shayne Waldron

Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand e–mail: [email protected] (http://www.math.auckland.ac.nz/˜waldron)

ABSTRACT

The Bernstein operator Bn for a simplex in IRd is naturally defined via the Bernstein basis obtained from the barycentric coordinates given by its vertices. Here we consider a generalisation of this basis and the Bernstein operator, which is obtained from generalised barycentric coordinates that are given for more general configurations of points in IRd. We call the associated polynomials a Bernstein frame, as they span the polynomials of degree ≤ n, but may not be a basis. By using this redundant system we are able to give geometrically motivated proofs of some basic properties of the corresponding generalised Bernstein operator, such as the fact it is degree reducing and converges for all polynomials.

We also consider the conditions for polynomials in this Bernstein form to join smoothly.

Key Words: multivariate Bernstein operator, barycentric coordinates, frames, redundant system Stirling numbers, blossoming, de Casteljau algorithm

AMS (MOS) Subject Classifications: primary 41A10, 41A36 65D17, secondary 15A18, 42C15,

(2)

### 1. Introduction

The Bernstein operator [L53] and its variants [AC94] have important applications, e.g., B´ezier curves and surfaces [F02]. Here we consider a generalisation of this operator, which is based on a redundant “Bernstein basis”.

The Bernstein operator Bn for a simplex in IRd is defined via the Bernstein basis for Πn(IRd) (thed–variate polynomials of degree≤n). This basis is obtained by taking powers of the barycentric coordinates given by the vertices of the simplex. In the next section, we outline the basic properties of generalised barycentric coordinates which are given by more general configurations of points in IRd, e.g., the vertices of a convex polygon. These lead naturally to an analogue of the Bernstein basis, a set of polynomials of degree n which span Πn(IRd). These are not a basis if they are given by more than d+ 1 points, and so we refer to this possibly redundant system as a Bernstein frame (cf. [C03]).

In Section 3, we define the generalised Bernstein operator given by a Bernstein frame.

We give geometrically motivated proofs of some basic properties of it. These include show- ing that it is degree reducing and converges for all polynomials, that it reproduces the linear polynomials, and more generally has the same spectral structure as the classical Bernstein operator. Similar arguments in terms of a basis would be far more cumbersome. Finally, we explore some applications of our generalised Bernstein operator. These include a de Casteljau algorithm, shape preservation properties (Section 4), and smoothness conditions in terms of the control points of the associated B´ezier surfaces (Section 5).

### 2. The Bernstein frame

Let V consist of d+ 1 affinely independent points in IRd, i.e., be the vertices of a d–

simplex. Thebarycentric coordinates(cf. [B87],[LS07]) of a pointx∈IRd with respect to V are the unique coefficients (ξv(x))v∈V ∈ IRV for which x can be written as an affine combination of the points in V, i.e.,

x= X

v∈V

ξv(x)v, X

v∈V

ξv(x) = 1. (2.1)

We follow [B87] and index the barycentric coordinates by the points v ∈ V that they correspond to, and use standard multiindex notation. It follows, from (2.1), that the ξv

are linear polynomials which are a basis for Π1(IRd). More generally, for any n ≥ 1, the polynomials

Bα :=

|α|

α

ξα, |α|=n (α ∈ZZV+) are a basis for Πn(IRd). Here |α|=P

vαv, nα

= n!α!, and ξα =Q

vξvαv.

From now on, letV be a sequence (or multiset) ofm=|V|points with affine hull IRd, so that each point x∈IRd can be written as an affine combination

x= X

v∈V

avv, X

v∈V

av = 1, (2.2)

(3)

where the coefficients a = (av)v∈V are unique if and only if V consists of d+ 1 points.

Following [W112], we call the unique minimal ℓ2–norm coefficientsa ∈IRV satisfying (2.2) the (generalised barycentric)coordinatesgiven byV, and denote them by (ξv(x))v∈V. By construction, they satisfy (2.1). Each ξv is a linear polynomial, and they span Π1(IRd), since (2.1) gives

1 = X

v∈V

ξv(x), xj = X

v∈V

ξv(x)vj, j = 1, . . . , d, (2.3)

which is equivalent to the following reproduction formula for affine functions f = X

v∈V

f(v)ξv, ∀f ∈Π1(IRd). (2.4) From the formula for ξv given in [W112] it is easy to see:

• The coordinates of the barycentre c:= m1 P

v∈V v of V are ξv(c) = m1 , ∀v.

• ξv is constant (equal to m1) if and only if v is the barycentre c.

• ξvw if and only if v=w.

• The ξv are continuous functions of the points v ∈V (with affine hull IRd).

These imply that the set of points where the coordinates are nonnegative

NV :={x∈IRdv(x)≥0,∀v∈V} (2.5) is a convex polytope, with the barycentre ofV as an interior point. We callNV theregion of nonnegativity for the coordinates given by V (See Fig. 1).

Fig 1. The region of nonnegativityNV for V given by the vertices of a triangle, square and pentagon.

We write V \w for the sequence (or multiset) obtained by removing the point w from V (once), and Aff(V) for the affine hull of the points inV. We recall:

Proposition 2.6 ([W112]). The generalised barycentric coordinates satisfy (a) m1 < ξv(v)≤1.

(b) ξv(w) =ξw(v).

(c) ξv(v) = 1if and only if v6∈Aff(V \v), in which case ξv = 0 on Aff(V \v).

(4)

(d) P

vξv(v) =d+ 1.

Expanding the monomial basis for Πn(IRd) in terms of ξ using (2.3), shows that the polynomials

Bα :=

|α|

α

ξα, |α|=n (2.7)

span Πn(IRd). By a dimension count, these n+m−1m−1

polynomials are basis if and only if V consists of d+ 1 affinely independent points. Thus, we refer to {Bα : |α| = n} as the Bernstein frame given by the points V. This is a partition of unity, since applying the multinomial theorem to (2.1) gives

X

|α|=n

Bα = X

|α|=n

n α

ξα = X

v∈V

ξv

n

= 1. (2.8)

A Bernstein frame is nonnegative onNV, the region of nonnegativity given by (2.5). There have been studies of the approximation properties of linear operators given by partitions of unity which may take negative values on the region of interest, see, e.g., [BD85].

Example 2.9. (See Fig. 2) For V ={0,12,1} ⊂IR the generalised barycentric coordinates are

ξ0(x) = 5

6 −x, ξ1

2(x) = 1

3, ξ1(x) =x− 1 6.

Here, some polynomials in the Bernstein frame have degree < n. This is the case if and only if the barycentre of V is a point of V. The coordinates for V ={0,13,23,1} are

ξ0(x) = 7 10 − 9

10x, ξ1

3(x) = 2 5 − 3

10x, ξ2

3(x) = 3

10x+ 1

10, ξ1(x) = 9 10x− 1

5.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

−0.2

−0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

−0.2

−0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7

Fig. 2. The Bernstein frame for Π2(IR) for V ={0,12,1} and V ={0,13,23,1}.

We say a polynomial p∈Πn(IRd) is in (Bernstein-B´ezier) B-formif

p= X

|α|=n

cαBα, (2.10)

(5)

The mesh function c : α 7→ cα is unique if and only if V consists of d+ 1 points. The mesh function with minimalℓ2–norm gives a canonical B-form, i.e., what[W111] calls the canonical coordinates of p with respect to {Bα}|α|=n.

Many familiar formulas for the Bernstein basis extend to a Bernstein frame. Here are a couple of examples (also see Section 4). Let ev be the multiindex given by

ev(w) :=

1, v=w;

0, and define Bα := 0 if α6≥0.

Proposition 2.11. The Bernstein frame {Bα}|α|=n can be calculated recursively via Bα = X

v∈V

ξvBα−ev, B0 = 1, (2.12)

and expressed in terms of the Bernstein frame for polynomials of degree n+ 1 via Bα = X

v∈V

αv+ 1

|α|+ 1Bα+ev. (2.13)

Proof: We calculate X

v∈V

ξvBα−ev = X

v∈V

|α| −1 α−ev

ξα = X

v∈V

αv

|α|

|α|

α

ξα =Bα, and, using P

vξv = 1, that Bα =Bα

X

v∈V

ξv = X

v∈V

|α|!

α! ξαξv = X

v∈V

αv+ 1

|α|+ 1

|α+ev|!

(α+ev)!ξα+ev = X

v∈V

αv + 1

|α|+ 1Bα+ev.

Proposition 2.14 (Differentiation). For u, v, w ∈V, we have Dv−wξuu(v)−ξu(w) =ξv(u)−ξw(u).

Thus the Bernstein frame satisfies

Dv−wBα =|α|X

u∈V

ξu(v)−ξu(w)

Bα−eu. Proof: Sinceξu is affine

(Dv−wξu)(x) = lim

t→0

ξu(x+t(v−w))−ξu(x) t

= lim

t→0

ξu(x) +tξu(v)−tξu(w)−ξu(x)

t =ξu(v)−ξu(w).

By the product and chain rules, we have Dv−wBα = |α|!

α! Dv−w Y

u∈V

ξuαuξα−αueu = |α|!

α!

X

u∈V

αuξuαu−1 ξu(v)−ξu(w)

ξα−αueu

=|α|X

u∈V

ξu(v)−ξu(w)(|α| −1)!

(α−eu)!ξα−eu =|α|X

u∈V

ξu(v)−ξu(w)

Bα−eu.

(6)

### 3. The generalised Bernstein operator

For a Bernstein frame (2.7) given by points V in IRd, we define a (generalised) Bernstein operator Bn =Bn,V of degree n≥1 by the usual formula

Bn(f) := X

|α|=n

Bαf(vα), vα := X

v∈V

αv

|α|v, (3.1)

which is equivalent to

Bn(f) = X

v1∈V

· · · X

vn∈V

fv1+· · ·+vn n

ξv1· · ·ξvn.

Fig. 3. The points {vα}|α|=n used in the definition of Bn,Vf, where n= 7 and V is the vertices of a triangle, square, pentagon and hexagon (respectively).

This maps functionsf which are nonnegative at the points (vα)|α|=k (which are contained in T = conv(V), the convex hull of the points in V) to polynomials of degree ≤n which are nonnegative on the convex polytope (region of nonnegativity) NV given by (2.5), so that

f ≥0 on T =⇒ Bnf ≥0 on NV, (3.2)

and reproduces the linear polynomials (cf. Theorem 3.19).

We now show that the generalised Bernstein operator is degree reducing, i.e., Bn(f)∈Πk(IRd), ∀f ∈Πk (k = 0,1, . . .).

Define the univariate and multivariate (falling) shifted factorials by [x]n:=x(x−1)· · ·(x−n+ 1), [α]β := Y

v∈V

v]βv, and the multivariate Stirling numbers of the second kind by

S(τ, β) := Y

v∈V

S(τv, βv),

where S(τv, βv) are the Stirling numbers of the second kind. We note that

S(τ, β) = 0, β 6≤τ, (3.3)

(7)

and define

|α|

α

:= 0, α 6≥0. (3.4)

These are related by

ατ = X

β≤τ

S(τ, β)[α]β. (3.5)

Lemma 3.6. For any τ and n, we have X

|α|=n

ατ |α|

α

ξα = X

β≤τ

S(τ, β)[n]|β|ξβ. (3.7)

Proof: Since [|α|]|β| |α−β|α−β

= |α|α

[α]β (without restriction on α and β), (3.5) gives

X

β≤τ

S(τ, β)[|α|]|β|

|α−β|

α−β

= |α|

α X

β≤τ

S(τ, β)[α]β = |α|

α

ατ. Thus, we calculate

X

|α|=n

ατ |α|

α

ξα = X

|α|=n

X

β≤τ

S(τ, β)[|α|]|β|

|α−β| α−β

ξα

= X

β≤τ

S(τ, β)[n]|β|ξβ X

|α|=n α≥β

|α−β|

α−β

ξα−β = X

β≤τ

S(τ, β)[n]|β|ξβ,

with the last equality given by the multinomial identity.

Theorem 3.8 (Degree reducing). The generalised Bernstein operator Bn is degree reducing. More precisely,

Bnβ) = [n]|β|

n|β| ξβ + X

0<|γ|<|β|

[n]|γ|

n|β| a(γ, β)ξγ, (3.9) where w1, . . . , wm is the sequence of points in V, and

a(γ, β) := X

1|=βw1

· · · X

m|=βwm

βw1

τ1

ξτ1(w1)· · · βwm

τm

ξτm(wm)S(τ1+· · ·+τm, γ).

(3.10) Proof: Since each ξw is an affine function, and ξw(v) =ξv(w), we have

ξw(vα) =ξw

X

v∈V

αv

|α|v

= X

v∈V

αv

|α|ξw(v) = X

v∈V

αv

|α|ξv(w),

(8)

and the multinomial identity gives (ξβ)(vα) = Y

w∈V

X

v∈V

αv

|α|ξv(w)βw

= Y

w∈V

X

|τ|=βw

βw

τ

ατ

|α|βwξτ(w)

= X

1|=βw1

· · · X

m|=βwm

βw1

τ1

· · · βwm

τm

ξτ1(w1)· · ·ξτm(wmτ1+···+τm

|α||β| . Thus, by rearranging (3.1) and Lemma 3.6, we have

Bnβ) = X

1|=βw1

· · · X

m|=βwm

βw1 τ1

ξτ1(w1)· · · βwm

τm

ξτm(wm) X

|α|=n

ατ1+···+τm n|β|

n α

ξα

= X

1|=βw1

· · · X

m|=βwm

βw1 τ1

ξτ1(w1)· · · βwm

τm

ξτm(wm)

× X

γ≤τ1+···+τm

[n]|γ|

n|β| S(τ1+· · ·+τm, γ)ξγ.

Here Bnβ) is written as a polynomial in ξ of degree≤ |β|, so thatBn is degree reducing.

The terms of degree |β| can be simplified using the multinomial identity, ξv(wj) =ξwj(v), and (2.4), as follows

X

1|=βw1

· · · X

m|=βwm

βw1

τ1

ξτ1(w1)· · · βwm

τm

ξτm(wm)[n]|β|

n|β| ξτ1+···+τm

= [n]|β|

n|β|

Ym

j=1

X

j|=βwj

βwj τj

ξτj(wjτj

= [n]|β|

n|β|

Ym

j=1

X

v∈V

ξv(wjv

βwj

= [n]|β|

n|β|

Ym

j=1

X

v∈V

ξwj(v)ξv

βwj

= [n]|β|

n|β|

Ym

j=1

ξwβwjj = [n]|β|

n|β| ξβ.

By collecting the terms of degree < |β|, we obtain (3.9). Here, (3.3) allows us to remove the restrictionγ ≤τ1+· · ·+τm, and there are no terms of degree 0 since S(1,0) = 0.

Remark 3.11. If V consists of d+ 1 affinely independent points, then a(γ, β) =

S(β, γ), γ ≤β;

0, γ 6≤β,

and (3.9) simplifies to

Bnβ) = [n]|β|

n|β| ξβ+ X

γ<β

[n]|γ|

n|β| S(β, γ)ξγ.

(9)

This was proved in [CW02](Lemma 2.1) for the case when βv0 = 0 for some v0 ∈V. Example 3.12 (Linear reproduction). For |β|= 1, we have

Bnv) =ξv, ∀v∈V, (3.13)

i.e., Bn reproduces the linear polynomials Π1(IRd) = span{ξv}v∈V. This is equivalent to

x = X

|α|=n

Bα(x)vα, X

|α|=n

Bα(x) = 1, x ∈IRd. (3.14)

Example 3.15 (Quadratics). For |β|= 2, we recall S(1,0) = 0,S(2,1) = 1, so that a(eu,2ew) =ξu2(v) =ξ2v(u), a(eu, ev +ew) =ξu(v)ξu(w) = (ξvξw)(u), v 6=w, (3.16) and we obtain

Bnβ) = 1− 1

n

ξβ + 1 n

X

u∈V

ξβ(u)ξu →ξβ, as n→ ∞, |β|= 2. (3.17)

SinceBn is not a positive operator in general, the application of the Korovkin theory is more involved (see Theorem 3.31). We easily obtain the following encouraging result.

Corollary 3.18 (Convergence). For all polynomialsf, Bn(f)→f, as n→ ∞.

Proof: It suffices to consider f =ξβ. For n≥ |β|, (3.9) gives Bnβ)−ξβ =[n]|β|

n|β| −1

ξβ − X

|γ|<|β|

[n]|γ|

n|β| a(γ, β)ξγ, where [n]n|β||β| −1,[n]n|β||γ| =O(1n), as n→ ∞.

The remaining eigenstructure of Bn is as follows.

Theorem 3.19 (Diagonalisation). The generalised Bernstein operator Bn given by points V ⊂IRd is diagonalisable, with eigenvalues

λ(n)k := [n]k

nk , k= 1, . . . , n, 1 =λ(n)1 > λ(n)2 >· · ·> λ(n)n >0.

Let Pk,V(n) denote the λ(n)k –eigenspace. Then

P1,V(n) = Π1(IRd), ∀n. (3.20)

For k >1, Pk,V(n) consists of polynomials of exact degree k, and is spanned by p(n)ξββ+ X

0<|α|<|β|

c(α, β, n)ξα, |β|=k, (3.21)

(10)

where the coefficients can be calculated using (3.10) and the recurrence formula c(α, β, n) := a(α, β)

1− |β|, |α|=|β| −1, c(α, β, n) := [n]|α|

λ(n)|β| −λ(n)|α|

a(α, β)

n|β| + X

|α|<|γ|<|β|

c(γ, β, n)a(α, γ) n|γ|

, |α|<|β| −1.

(3.22) Proof: By Example 3.12, theλ(n)1 = 1 eigenspace P1,V(n) contains Π1(IRd). Recall, from (3.9), that Bnβ) has the form

Bnβ) =λ(n)|β|ξβ+ X

0<|γ|<|β|

[n]|γ|

n|β| a(γ, β)ξγ. (3.23) Motivated by this, we seek λ(n)k –eigenfunctions of the form

f =ξβ+ X

0<|α|<|β|

c(α, β, n)ξα, |β|=k >1.

We observe that for such an eigenfunction the coefficients c(α, β, n) are not unique– even when V consists of d+ 1 points. Expanding Bn(f) =λ(n)k f using (3.23) gives

Bn(f) =Bnβ) + X

0<|γ|<|β|

c(γ, β, n)Bnγ)

(n)|β|ξβ+ X

0<|α|<|β|

[n]|α|

n|β| a(α, β)ξα + X

0<|γ|<|β|

c(γ, β, n)

λ(n)|γ|ξγ+ X

0<|α|<|γ|

[n]|α|

n|γ| a(α, γ)ξα

(n)|β|ξβ+ X

0<|α|<|β|

λ(n)|β|c(α, β, n)ξα.

(3.24) Equating the ξα, 0<|α|<|β| coefficients gives

λ(n)|β|c(α, β, n) = [n]|α|

n|β| a(α, β) +c(α, β, n)λ(n)|α| + X

|α|<|γ|<|β|

c(γ, β, n)[n]|α|

n|γ| a(α, γ). (3.25) Since λ(n)|α| > λ(n)|β|, this is equivalent to

c(α, β, n) = 1 λ(n)|β| −λ(n)|α|

[n]|α|

n|β| a(α, β) + X

|α|<|γ|<|β|

c(γ, β, n)[n]|α|

n|γ| a(α, γ) . From this we can define suitable c(α, β, n) recursively, as in (3.22), starting from

c(α, β, n) := 1 λ(n)|β| −λ(n)|α|

[n]|α|

n|β| a(α, β) = a(α, β)

1− |β|, |α|=|β| −1.

A simple dimension count shows that the eigenfunction {pξβ}|β|=k, so defined, span a space Pk,V(n) of dimension k+d−1d−1

. Again, by dimension counting, we conclude that Bn is diagonalisable, withP1,V(n) = Π1(IRd).

(11)

Example 3.26 (Quadratic eigenfunctions). Using (3.16), we have p(n)ξββ −X

u∈V

ξβ(u)ξu, |β|= 2. (3.27)

In general, p(n)ξα does depend on n (cf. [CW00]).

Despite the fact the coefficients in (3.21) are not unique, we can take their limit as n→ ∞. This indicates that the redundant expansion (3.21) is natural.

Corollary 3.28 (Limits of the eigenfunctions). For 0<|α|<|β|,

n→∞lim c(α, β, n) =c(α, β), where

c(α, β) := a(α, β)

1− |β|, |α|=|β| −1,

c(α, β) := 2

(|β| − |α|)(−|α| − |β|+ 1) X

|γ|=|α|+1

c(γ, β)a(α, γ), |α|<|β| −1. (3.29)

Thus, the eigenfunctions of (3.21) satisfy p(n)ξβ →pξβ :=ξβ + X

0<|α|<|β|

c(α, β)ξα, as n→ ∞. (3.30)

Proof: Fix β. We use strong induction on j = |β| − |α| = 1, . . . ,|β| to prove the limit exists. For |α| = |β| −1 (j = 1) the limit is clear. Suppose the limit of c(γ, β, n) exists for all γ with |α|<|γ|<|β|. Then taking the limit of (3.22) gives

n→∞lim c(α, β, n) = 2

(|β| − |α|)(|β| − |α| −2|β|+ 1) X

|γ|=|α|+1

c(γ, β)a(α, γ).

This follows from the calculations λ(n)|β| −λ(n)|α| = [n]|α|[n− |α|]|β|−|α|

n|β| − [n]|α|

n|α| = [n]|α|

n|β| ([n− |α|]|β|−|α|−n|β|−|α|), [n− |α|]|β|−|α|−n|β|−|α| = 1

2(|β| − |α|)(−|α| − |β|+ 1)n|β|−|α|−1+ lower order powers of n.

Since p(n)ξβ , pξβ ⊂Π|β|(IRd), we have the convergence asserted in (3.30).

(12)

We now prove the strongest Korovkin theorem that the restricted positivity property (3.2) allows. Since this requires a modification of the usual argument, which is not stated in the literature, we give a self contained proof. This result supercedes Corollary 3.18.

Theorem 3.31 (Korovkin). Let T =TV be the convex hull of V, and NV be the region of nonnegativity. For f ∈C(T), Bnf →f uniformly on NV.

Proof: Let ε > 0, and M be the maximum of f over T. Since f is uniformly continuous on the compact set T, there is aδ >0 such that |f(s)−f(t)|< ε, ∀ks−tk< δ.

Thus, we obtain the estimate

|f(s)−f(t)| ≤ε+ 2Mks−tk2

δ2 , ∀s, t∈T, For fixed t, we have

−ε− 2M

δ2 k · −tk2 ≤f−f(t)≤ε+ 2M

δ2 k · −tk2 onT , and so applying Bn (which reproduces constants) and using (3.2) gives

−ε− 2M

δ2 Bn k · −tk2

≤Bnf −f(t)≤ε+ 2M

δ2 Bn k · −tk2

on NV. This last step is the main difference in argument. For t ∈NV, evaluating at t gives

|Bnf(t)−f(t)| ≤ε+ 2M

δ2 Bn k · −tk2

(t), ∀t∈NV. (3.32) We now estimate Bn(k · −tk2)(t). From (2.1), we obtain

k · −tk2 =hX

v

vv−ξvt},X

w

ww−ξwt}i=X

v

X

w

ξvξwhv−t, w−ti.

Thus, (3.17) gives Bn k · −tk2

=X

v

X

w

n 1− 1

n

ξvξw+ 1 n

X

u∈V

ξv(u)ξw(u)ξu

o

hv−t, w−ti

= 1− 1

n

k · −tk2+ 1 n

X

v

X

w

X

u∈V

ξv(u)ξw(u)ξuhv−t, w−ti

= 1− 1

n

k · −tk2+ 1 n

X

u∈V

ξuhu−t, u−ti, so that

Bn k · −tk2

(t) = 1 n

X

u∈V

ku−tk2ξu(t) = 1 n

X

u∈V

kuk2ξu(t)− ktk2

≤ 1 nD2, where D:= diam(T) is the diameter of T. Thus, we obtain the uniform estimate

|Bnf(t)−f(t)| ≤ε+ 1 n

2M D2

δ2 , t ∈NV, and conclude that Bnf →f uniformly on NV.

(13)

### 4. Applications to CAGD

We now consider how our generalised Bernstein operator Bn = Bn,V might be used in CAGD (computer aided geometric design) to describe polynomials defined on convex polyhedra which are not simplices. We first observe that the Korovkin theory does not allow a Bernstein type operator which is positive on the entire region T = conv(V) if the points of V are not the vertices of a simplex or a cube.

Theorem 4.1 ([MRS94]). LetT be a convex polygon with five or more vertices. There is no positive linear operator L:C(T)→C(T)which reproduces Π1(IR2) and maps Π2(IR2) to itself other than the identity.

We recall, that our Bn reproduces Π1(IR2) and maps Π2(IR2), but has the restricted positivity property (3.2), i.e.,

f ≥0 on T =⇒ Bnf ≥0 on NV,

where NV is the region of nonnegativity (2.5). In the multivariate case, the description of other shape preserving properties is involved (cf. [S91]). We mention some which do generalise easily. These suggest that the target region for representing polynomials on should perhaps be the convex polyhedron NV, rather than T = conv(V).

Proposition 4.2 (Shape preservation). Let T =TV be the convex hull of V, andNV

be the region of nonnegativity. If f is convex onT, then

Bnf ≥Bn+1f ≥ · · · ≥f on NV. (4.3) Proof: Fixx∈NV. By (2.1), and a calculation, we have the convex combinations

x= X

|α|=n

Bα(x)vα, vβ = X

v∈V

βv

|β|vβ−ev. Hence for f convex, Jensen’s inequality gives

Bnf(x) = X

|α|=n

Bα(x)f(vα)≥f(x), X

v∈V

βv

|β|f(vβ−ev)≥f(vβ). (4.4) By the degree raising formula (2.13), we have

Bnf = X

|α|=n

Bαf(vα) = X

v∈V

X

|α|=n

αv + 1

|α|+ 1Bα+evf(vα), so that

Bnf−Bn+1f = X

|β|=n+1

cβBβ, cβ := X

v∈V

βv

|β|f(vβ−ev)−f(vβ).

By (4.4), cβ ≥0, so that Bnf ≥Bn+1f on NV.

(14)

A polynomial in B-form can be calculated via the de Casteljau algorithm. We present this in terms of the blossom (polar form) of a polynomial p∈Πn(IRd), which we recall (cf. [R89], [DLG91], [DMS92]) is the unique symmetric n–affine function ωp with

ωp(t, . . . , t) =p(t), ∀t ∈IRd. (4.5) Proposition 4.6 (de Casteljau algorithm). Suppose that p∈Πn(IRd) has the B-form

p= X

|α|=n

cαBα. (4.7)

Then the blossom of p at t1, . . . , tn can be calculated from (cα)|α|=n via for j = 1 to n do

cα := X

v∈V

ξv(tj)cα+ev, |α|=n−j end for

with c0 =ωp(t1, . . . , tn). In particular, taking t1 =· · ·=tn =t gives c0 =p(t).

Proof: Suppose p∈Πn(IRd) is in the B-form (4.7), i.e., equivalently p=X

v1

· · ·X

vn

cev

1+···+evnξv1· · ·ξvn. (4.8) Then its blossom is given by

P(t1, . . . , tn) :=X

v1

· · ·X

vn

cev1+···+evnξv1(t1)· · ·ξvn(tn), (4.9) since P clearly defines an n–affine function, which, by (4.8), satisfies (4.5). The n steps of the algorithm are the averagings given by the n sums in (4.9).

In the terminology of [DMS92], this is a symmetric simplicial algorithm (here the points V need not be the vertices of a simplex).

The coefficients cα in the B-form (4.7) of p are not unique, unlessV is the vertices of a simplex. Using (2.1) to expand, we have

p(t) =ωp(t, . . . , t) =ωp(X

v1

ξv1(t)v1, . . . ,X

vn

ξvn(t)vn)

=X

v1

· · ·X

vn

ξv1(t)· · ·ξvn(t)ωp(v1, . . . , vn), and so the coefficients cα in (4.7) can be chosen to be the blossoms

bα =ωp(α·V), α·V := (. . . , v, . . . , v

| {z }

αv times

, . . .), (4.10)

which we call the blossoming coefficients.

(15)

Proposition. For any p of the form (4.7), the blossoming coefficients b = (bα)|α|=n are given by the matrix multiplication

b=Qc, Q= [qαβ]|α|=n,|β|=n, qαβ :=Bωβ(α·V).

For n >1, our calculations show that the blossoming coefficients are not the ℓ2–norm minimising choice (which is given by multiplication by an orthogonal projection matrix).

Remark 4.11. The previous discussion extends to p = (p1, . . . , ps) : IRd → IRs, where pj ∈Πn(IRd) and cα ∈IRs, by considering coordinates. Since vector valued p are used in practice, e.g., B´ezier curves in IR3, we henceforth state our results in this setting.

We define the control points of the curve (d = 1), surface (d = 2), etc, given by t7→p(t)∈IRs, where p has B-form (4.7), to be

nvα cα

:|α|=no

⊂IRd+s.

Since the B-form is not unique when V has more thand+ 1 points, a given curve (surface, etc) may be given by different sets of control points. This redundancy has advantages from the point of view of design, as a given surface could be arrived at by a number of different choices of control points. Equivalently, each control point has less influence on the the surface, and so moving a control point causes a small change of shape making the fine tuning of a surface easier. Once a suitable surface has been obtained it can be presented in terms of a set of canonical control points – if so desired.

By combining (3.14) and (4.7), we have x

p(x)

= X

|α|=n

cαBα(x), cα :=

vα

cα

. (4.12)

Thus a point x, p(x)

on the curve (surface, etc) can be calculated by the de Casteljau algorithm applied to the vectors (cα)|α|=n ⊂IRd+s. Many basic properties of B´ezier curves and surfaces follow from (4.12). We now list these using the terminology of [F02].

Convex hull property: Since P

|α|=nBα(x) = 1 and Bα(x) ≥ 0, x ∈ NV, the point x, p(x)

is an affine combination (also called a barycentric combination in CAGD) of the control points (cα)|α|=n, which is a convex combination if x∈NV.

Affine invariance: For A : IRs →IR an affine map, we have A p(x)

= X

|α|=n

(Acα)Bα(x).

Invariance under affine parameter transformations: ForA: IRd →IRd an invertible affine map, Bα(Ax) =A(Bα(x)), so that

p(Ax) = X

|α|=n

cαA Bα(x) .

(16)

Symmetry: Suppose that A is an affine map which maps (the multiset) V to V. Then ξv(x) =ξAv(Ax) (see [W112]), so that

Bα(x) =Bα◦A−1(Ax),

where α◦A−1 :V →ZZ+ denotes the multiindex v7→αA−1v. Using this we obtain p(x) = X

|α|=n

cαBα(x) = X

|α|=n

cαBα◦A−1(Ax) = X

|β|=n

cβ◦ABβ(Ax).

Invariance under barycentric combinations: The affine combination of two curves (surfaces, etc) is given by corresponding affine combination of the control points, i.e.,

λ X

|α|=n

bαBα(x) + (1−λ) X

|α|=n

cαBα(x) = X

|α|=n

λbα + (1−λ)cα Bα(x), λ∈IR.

Endpoint interpolation: If v∈V satisfies v6∈Aff(V \v), then Prop. 2.6 gives (Bnf)(v) =f(v).

The remaining property given in[F02]ispseudolocal control, i.e., the fact thatBα is peaked at the point vα, and so moving the control point cα has the most influence on the curve (surface, etc) near the point vα. Numerical calculations indicate some degree of localisation of the Bα near vα, but we do not make any quantitative statements here.

To summarise, the main features of our Bernstein polynomial approximations on a nonsimplicial convex polytope are:

• A surface may be determined by several different choices of control points.

• Moving the control points has less influence on the shape if there are many of them.

• On NV the surface is a convex combination of the control points.

• Convex functions are monotonely approximated from above by Bn on NV.

Typical applications, that require a single polynomial defined on a convex polytope, include the description and construction of finite elements on regular polygons and the design of hexagonal lenses (cf. [D87]).

### 5. Smoothness and multivariate splines

We now consider the possible application of our results to multivariate spline theory, where surfaces are constructed by joining polynomial pieces together smoothly. There is a highly developed theory (and associated software) that involves polynomials defined on simplices, based on the description of the smoothness conditions in terms of the control

(17)

points (cf. [B87], [LS07]). We assume that the reader is familiar with this, and we inves- tigate how it extends to partitions involving nonsimplical cells. There was work in this direction (see [L89], [CL90]) on mixed grid partitionswhere in the bivariate case the cells were trianglesandparallelograms, and in the trivariate case they weretetrahedrons,prisms and parallelopipeds. The B-form developed for nonsimplicial cells was for polynomials of coordinate degree n (as were the spline spaces), rather than total degree n, though the positioning of the control points is the same as we propose. Bivariate C1–quadratics on a polygonal partition were considered in [Wh90].

We will give our results in terms of the blossoming coefficients. The following is adapted from the[B87],[R89]and[L91](cf.[W13]). If (cα) are the blossoming coefficients, then we refer to the (cα) of (4.12) as the blossoming control points of p = P

cαBα. Let

r·x:=x, . . . , x

| {z }

r times

,

Theorem 5.1.. LetW be a set of points inIRd, with L= Aff(W). Then the polynomials f, g ∈Πn(IRd) have all derivatives of order ≤r onL equal if and only if

ω

f(w1, . . . , wn−r, r·x) =ωg(w1, . . . , wn−r, r·x), w1, . . . , wn−r ∈W, x∈IRd. (5.2) Let

α·V := (. . . , v, . . . , v

| {z }

αv times

, . . .), α∈ZZ+V.

Lemma 5.3. Let cbe the blossoming coefficients of (4.10) for p∈Πn(IRd). Then

ωp(α·V, r·x) = X

|β|=r

cα+βBβ(x), |α|=n−r, r = 0, . . . , n.

Proof: Since the blossomωp is n–affine, we have

ωp(α·V, r·x) =ωp(α·V, X

v1∈V

ξv1(x)v1, . . . , X

vr∈V

ξvr(x)vr)

= X

v1∈V

· · · X

vr∈V

ξv1(x)· · ·ξvr(x)ωp(α·V, v1, . . . , vr)

= X

|β|=r

cα+βBβ(x).

(18)

Combining Theorem 5.1 and Lemma 5.3 gives smoothness conditions for the Cr– joining of polynomials in terms of their blossoming B–form coefficients.

We now illustrate this for C1–quadratics on a region consisting of a triangle and a quadrilateral with a common edge.

Example 5.4 (C1–quadratics on triangle and quadrilateral). Without loss of gen- erality, suppose the vertices of the triangle and quadrilateral are

V ={v1, . . . , v3}={0, e1, a}, a2 6= 0, V˜ ={˜v1, . . . ,v˜4}={0, e1, b,−e2}, so the common edge has endpoints v1 = ˜v1 = 0. and v2 = ˜v2 =e1 = (1,0). We index the generalised barycentric coordinatesξ and ˜ξ by both their order and the points themselves, e.g., ξ3 and ξa(a1,a2), whichever is the most convenient. We have

ξ1(x, y) = (1−x) + a1−1

a2 y, ξ2(x, y) =x− a1

a2y, ξ3(x, y) = 1 a2y, ξ˜(0,0)(x, y) = −(b22+b1b2+b1+ 1)x+ (b21+b1b2−b1+ 1)y+b21+b22+ 1

2(b21+b22−b1b2+b2−b1+ 1)

ξ˜(1,0)(x, y) = (2b22−b1b2+ 2b2−b1+ 2)x+ (b21−2b1b2−b1)y+b21−b1b2−b1 2(b22+b2+ 1−b1b2−b1+b21) , ξ˜(b1,b2)(x, y) = (2b1−b2−1)x+ (2b2−b1+ 1)y+b2−b1+ 1

2(b22+b2+ 1−b1b2−b1+b21) ,

ξ˜(0,−1)(x, y) = (−b22+ 2b1b2−b2)x+ (−2b21+b1b2+ 2b1−b2−2)y+b22−b1b2+b2 2(b22+b2+ 1−b1b2−b1+b21) , Suppose that f, g ∈Π2(IR2) are quadratics with blossoming coeffient B–forms

f = X

|ga|=2 α∈ZZV

+

cαBα, g= X

|ga|=2 α∈ZZV˜ +

˜ cαα.

In Theorem 5.1, we take n= 2, and

W ={v1, v2}={˜v1,v˜2}={0, e1}.

For r = 0, the condition forf and g to have a continuous join on the line L= Aff(W) is given by the two element sequences from W ={v1, v2}, i.e.,

ω

f(v1, v1) =ωg(v1, v1), fω(v1, v2) =ωg(v1, v2), ωf(v2, v2) =ωg(v2, v2).

which by Lemma 5.3 is

c(2,0,0) = ˜c(2,0,0,0), c(1,1,0) = ˜c(1,1,0,0), c(0,2,0) = ˜c(0,2,0,0).

(19)

For r = 1, the condition for f and g to have a C1–join on L is given by the one element sequences from W ={v1, v2}, i.e.,

ωf(v1, x) =ωg(v1, x), fω(v2, x) =ωg(v2, x).

By Lemma 5.3, these equalities of linear polynomials in x can be written

c(2,0,0)ξ1+c(1,1,0)ξ2+c(1,0,1)ξ3 = ˜c(2,0,0,0)ξ˜1+ ˜c(1,1,0,0)ξ˜2+ ˜c(1,0,1,0)ξ˜3+ ˜c(1,0,0,1)ξ˜4, c(1,1,0)ξ1+c(0,2,0)ξ2+c(0,1,1)ξ3 = ˜c(1,1,0,0)ξ˜1+ ˜c(0,2,0,0)ξ˜2+ ˜c(0,1,1,0)ξ˜3+ ˜c(0,1,0,1)ξ˜4. Since the blossoming control points for the quadrilateral are simply those for corresponding triangles, it follows that these smoothness conditions have the usual geometric interpreta- tion: that all the control points involved (3 and 4 respectively, see Fig. 4) lie in a common plane.

Fig. 4. The C1–smoothness conditions of Example 5.4.

### 6. Future work

For applications where it is desirable to have generalised barycentric coordinates which are nonnegative on the convex hull of V, one could modify the definition of (ξv(x))v∈V for x∈conv(V) to be the unique minimal ℓ2–norm coefficients a∈IRV satisfying

x= X

v∈V

avv, X

v∈V

av = 1, av ≥0. (6.1)

With this definition ξv is a continuous piecewise linear polynomial, which coincides with with the original on NV.

### References

[AC94] F. Altomare and M. Campiti, “Korovkin-type approximation theory and its applica- tions”, Walter de Gruyter, Berlin, 1994.

(20)

[B87] C. de Boor, B-form basics, in “Geometric Modeling: Algorithms and New Trends”

(G. E. Farin Ed.), pp. 131–148, SIAM Publications, Philadelphia, 1987.

[BD85] C. de Boor and R. DeVore, Partitions of unity and approximation,Proc. Amer. Math.

Soc. 93 (1985), 705–709.

[C03] O. Christensen, “An introduction to frames and Riesz bases”, Birkh¨auser, Boston, 2003.

[CL90] C. K. Chui and M.-J. Lai, Multivariate vertex splines and finite elements,J. Approx.

Theory 60 (1990), 245–343.

[CW00] S. Cooper and S. Waldron, The eigenstructure of the Bernstein operator, J. Approx.

Theory 105 (2000), 133-165.

[CW02] S. Cooper and S. Waldron, The diagonalisation of the multivariate Bernstein operator, J. Approx. Theory 117 (2002), 103–131.

[DMS92] W. Dahmen, C. A. Micchelli, and H.-P. Seidel, Blossoming begetsB-spline bases built better by B-patches, Math. Comp. 59(1992), 97–115.

[DLG91] T. DeRose, M. Lounsbery, and R. Goldman, A tutorial introduction to blossoming, Comput. Graph. Systems Appl. (1991), 267–286.

[D11] Tan Duc Do, Generalised Bernstein operators on polytopes, Honours dissertation, 2011.

[D87] C. F. Dunkl, Orthogonal polynomials on the hexagon, SIAM J. Appl. Math. 47 (1987), 343–351.

[F02] G. Farin, “Curves and surfaces for computer-aided geometric design: A practical guide (5th ed.)”, Academic Press, San Diego, 2002.

[L89] M.-J Lai, On construction of bivariate and trivariate vertex splines on arbitrary mixed grid partitions, Dissertation (Texas A & M Univ.), 1989.

[L91] Ming Jun Lai, A characterization theorem of multivariate splines in blossoming form, Comput. Aided Geom. Design 8 (1991), 513-521.

[LS07] M.-J. Lai and L. L. Schumaker, “Spline functions on triangulations”, Cambridge Uni- versity Press, Cambridge, 2007.

[L53] G. G. Lorentz, “Bernstein Polynomials”, Toronto Press, Toronto, 1953.

[MRS94] F.-J. Mu˜noz-Delgado, V. Ram´irez Gonz´alez, and T. Sauer, Domains for Bernstein polynomials, Appl. Math. Lett. 7 (1994), 7–9.

[S91] T. Sauer, Multivariate Bernstein polynomials and convexity, Comput. Aided Geom.

Design 8 (1991), 465–478.

[R89] L. Ramshaw, Blossoms are polar forms, Comput. Aided Geom. Design 6 (1989), 323- 358.

[W111] S Waldron, Frames for vector spaces and affine spaces, Linear Algebra Appl. 435 (2011), 77–94.

[W112] S Waldron, Affine generalised barycentric coordinates, Jaen J. Approx. 3 (2011), 209–226.

[W13] S Waldron, Blossoming and smoothly joining polynomials on affine subspaces, Preprint, 2013.

[Wh90] W. Whiteley, The geometry of bivariate C21-splines, Preprint, 1990.

References

Related documents

TA B L E 1   Coordinates for each site within the Gravel Plains of the Namib Desert from which springtail COI sequences were obtained, including number of sequences (n) and

I suggest that the encounter between Law &amp; Literature, like the one we are engaged in here, is similarly uncanny and provokes anxiety or disquiet because we are forced to

Although numerous studies (e.g., Ball, 1990, 1994; Bernstein, 2000) have identified the various processes and issues associated with realising educational policy intent,

The analogue of Solovay’s forcing is the addition of a measurable-length sequence of Cohen reals, equivalently forcing with the open subsets of the product space 2 κ for κ

We will first see that eigenvalues and eigenvectors are central to achieving this, and sometimes we need so-called generalised eigenvectors to obtain the general solution, but our

New suggests that here, in the sketches of local life rather than in the more formal fiction and poetry, is the reservoir from which later writing grew.” 2 Lawrence Jones, writing

5, it is proved that the range of an Omega operator has positive measure and that every 2-random real is in the range of some Omega operator.. This is not true for every

from these individual catalysts, which then catalyzes the given reaction. The reaction that creates such a com- pound is catalyzed by a general catalyst called “X”. These reactions

asymmetrical patterns, but symmetry comes more naturally to them (Giurfa et al, 1996).  Bees are not reflective animals, and it is hard to believe they deal in “relations of

This method is applied in the experiment reported here, which represents a more re- alistic farming situation where the emissions from both urine and dung are measured as they

We consider a general positional voting rule, derive linear equations and inequalities describing exactly whether or not a given voting situation is manipulable by a given subset of

Since we are interested here in bifurcations from stationary behaviour we show only curves of Hopf bifurcation, which we present for = 0.01 mm (a), = 0.001 mm (b), and for

Many frames which are optimal for applications are projectively unitary equivalent to one from a special class of frames, e.g., harmonic frames, SICs (equiangular tight frames with

This dissertation will investigate the properties of the generalised version of Bernstein operators on simplices, that is, Bernstein operators on polytopes via generalised

Sessional Com m ittee on the Environm ent 79.. A strong research and development effort, particularly into the integration of control methods, is essential to the

The result of the use of this equipment combined with the right cultures and attitudes now means that spillage – even minor leakage to the environment need not now occur and

• Additional High Conservation Value Vegetation (AHCVV) means areas of vegetation which were found during ground-truthing which would otherwise meet the definition of Existing

• It changes the standard input file of the child process to be the read end of the most recently created pipe.. So standard input will come from

Madam CHAIR: Mr Khattra says that you stopped allowing him to drive your taxi because he was a witness at the inquiry, the Public Accounts Committee, in to the taxi industry, what is

Ms LAWRIE (Leader of Government Business): Madam Speaker, I move – That, the Assembly refer the following matters to the Standing Orders Committee for inquiry and report to

It was concluded that a tight frame for the space of orthogonal polynomials of degree one under a special case of the generalised Jacobi weight exists, the corresponding frame

The linear combinations of iterates of the Bernstein operator considered in Section 6 (including iterated Boolean sums) are operators of this type.. Depending on the properties of

existence. In making such an estimate, the Government Printer was requested to take as understood that each author body would have its report printed by the