Algorithms and Identities for (q,h)-Bernstein Polynomials and (q,h)-Bezier Curves
--A Non-Blossoming Approach

Ilija Jegdi′c,Jungsook Larsonand Plamen Simeonov

1DepartmentofMathematics,TexasSouthernUniversity,Houston,TX77004,USA.

2Department of Mathematics and Statistics,University of Houston–Downtown, Houston,TX 77002,USA.

Algorithms and Identities for (q,h)-Bernstein Polynomials and (q,h)-Bezier Curves
--A Non-Blossoming Approach

Ilija Jegdi′c1,?,Jungsook Larson2and Plamen Simeonov2

1DepartmentofMathematics,TexasSouthernUniversity,Houston,TX77004,USA.

2Department of Mathematics and Statistics,University of Houston–Downtown, Houston,TX 77002,USA.

.We establish several fundamental identities,including recurrence relations, degree elevation formulas,partition of unity and Marsden identity,for quantum Bernstein bases and quantum B ′ezier curves.We also develop two term recurrencerelations for quantum Bernstein bases and recursive evaluation algorithms for quantum B′ezier curves.Our proofs use standard mathematical induction and other elementary techniques.

Bernstein polynomials,B′ezier curves,Marsden’s identity,recursive evaluation.

AMS SubjectClassif i cations:11C08,65DXX,65D15,65D17

1 Introduction and def i nitions

Bernstein bases are polynomial bases used as blending functions for the construction of B ′ezier curves and surfaces.These bases have been used extensively over the last half century in geometric modeling,computer aided geometric design(CAGD),and approximation theory.The main application of B ′ezier curves and surfaces is in mathematical modeling of curves and surfaces that are used in various real life problems.One essential property of a B ′ezier curve or a B ′ezier surface is that it can be computed very eff i ciently using aff i ne recursive evaluation algorithms.This is due to certain structural properties of the Bernstein basis functions that other polynomial bases do not possess.

The classical Bernstein polynomials were introduced by Bernstein in 1912 and have foundmany applications inapplied andcomputational mathematics since then.Theclassical B ′ezier curves and surfaces were introduced in 1962 by the French engineer PierreB ′ezier who worked for the French car manufacturer Renault.He used B ′ezier curves and surfaces to design and model aerodynamic car bodies[1].The q-Bernstein polynomials were introduced and studied only recently by G.Phillips and his collaborators[7]. The theory of quantum q-and h-B ′ezier curves in the context of the quantum q-and hblossoming was developed very recently by Goldman,Simeonov,and Zaf i ris[4,9,10].

In this paper,our main goal is to state and prove several of the most important properties of the(q,h)-Bernstein polynomials and(q,h)-B ′ezier curves such as recurrence relations,degree elevation algorithms,the partition of unity property,linear independence(polynomial basis),recursive evaluation algorithms,and a(q,h)-Marsden identity. This work extends and generalizes some analogous results of Goldman,Simeonov,and Zaf i ris[2,4,9,10]for q-and h-Bernstein polynomials and q-and h-B ′ezier curves.Most of our proofs will use the method of mathematical induction(with respect to the polynomial degree),instead of the blossoming techniques used by Goldman,Simeonov,and Zaf i ris[2,4,9,10],since we lack the machinery of the(q,h)-blossoming theory.The advantage of our approach is that we can establish all these important properties almost from scratch using only the very popular and well-understood induction argument,instead of the much less familiar theory of quantum blossoming.

We begin with some notation and terminology.Let g(t)=qt+h be a linear function, q/=0,?1.The j-th composition of the function g is def i ned by

We set g[0](t)=t.For example

Notice that

The(q,h)-Bernstein polynomials of degree n on the interval[a,b]are def i ned by[3]

and(a;q)ndenotes the q-shifted factorial def i ned by[8]

Therefore,we have the following limiting relation

where

are the classical Bernstein polynomials of degree n on the interval[a,b],[2].

The paper is organized as follows.In Section 2 we establish recurrence relations for the(q,h)-Bernstein polynomials.The degree elevation formula for the(q,h)-Bernstein polynomials is established in Section 3.The partition of unity property is given and proved in Section 4.We show that the(q,h)-Bernstein polynomials form a basis for the space of degree n polynomials in Section 5.Using the recurrence relations from Section 2,we derive two recursive evaluation algorithms for(q,h)-B ′ezier curves in Section 6. Degree elevation for(q,h)-B ′ezier surfaces is discussed in Section 7,and the proof of the (q,h)-Marsden identity is given in Section 8.We conclude the paper by discussing future work in Section 9.

2 Recurrence relations for the(q,h)-Bernstein polynomials

In this section we derive two recurrence relations for the(q,h)-Bernstein polynomials using the two recurrence relations for the q-binomial coeff i cients[6]:

Similarly,substituting(2.1b)into(1.2),we derive

3 Degree elevation formula for the(q,h)-Bernstein polynomials

First we need to f i nd coeff i cients c(n,k)and d(n,k)such that

Suppose we have found these coeff i cients.Then we can write

From the last equation and(1.2)it follows that

k=0,···,n.Eq.(3.2)expresses a(q,h)-Bernstein polynomial of degree n as a linear combination of two(q,h)-Bernstein polynomials of degree n+1.Now,we return to f i ndingthe coeff i cients c(n,k)and d(n,k).Comparing the like terms in(3.1),we obtain the linear system

since

From(3.3a)and(3.4)it follows that

From(3.2),(3.4),and(3.6)we obtain the degree elevation formula

4 Partition of unity

Proposition 4.1.The(q,h)-Bernstein polynomials satisfy the partition of unity property

Proof.To prove(4.1),we use induction with respect to n ≥ 0.

by the induction hypothesis.Therefore(4.1)is true for every n.

5 Polynomial basis

Proposition 5.1.The(q,h)-Bernstein polynomials of degree n form a basis for the space of polynomials of degree at most n.

Proof.It suff i ces to show that for every n ≥ 0 there exist coeff i cientssuch that

We use induction with respect to n.When n=0 we have(t;[a,b];q,h)=1.Assume that (5.1)is true for some degree n ≥ 0.We now prove(5.1)for degree n+1.

First,let 0 ≤ m ≤ n.By the induction hypothesis and the degree elevation equation (3.2)we have

where

k=0,···,n+1,and c(n,k)and d(n,k)are given by(3.6)and(3.4). Now consider the monomial tn+1.By the induction hypothesis

where by(1.2)the coeff i cientsandmust satisfy the equation

Equating the coeff i cients of t on the both sides of(5.3),we obtain

Equating the constant coeff i cients on both sides of(5.3)we obtain

Multiplying(5.4)by g[k](a)and adding to(5.5)yields

Solving the last equation for ?d(n,k)and applying(3.5),we get

Then from(5.5)and(5.6)it follows that

6 Recursive evaluation algorithms for(q,h)-B′ezier curves

A(q,h)-B ′ezier curve of degree n on the interval[a,b]is a polynomial curve of the form

Given a degree n polynomial P(t),the coef fi cientsin Eq.(6.1)are unique,because by Proposition 5.1 the(q,h)-Bernstein polynomials form a basis.These coef fi cients are called the control points of the(q,h)-B e′zier curve P(t).

Using recurrence relations(2.2)and(2.3),we can derive two recursive evaluation algorithms for(q,h)-B e′zier curves.Below we describe these two algorithms.

where the control points at level r+1 are

k=0,···,n?r?1.

At the last level n of this algorithm we get a single pointwhich gives the value of the B ′ezier curve at t,that is=P(t).

Similarly,substituting recurrence relation(2.3)into Eq.(6.2),we derive the second recursive evaluation algorithm for(q,h)-B ′ezier curves:

k=0,···,n ? r?1,r=0,···,n ? 1.Again,at the last level n we get=P(t).

7 Degree elevation for(q,h)-B ′ezier curves

Let

be a(q,h)-B ′ezier curve of degree n on the interval[a,b].We want to write P(t)as a(q,h)-B ′ezier curve of degree n+1,that is,

Substituting the degree-elevation formula(3.2)into(7.1),we get

where c(n,?1)=d(n,n+1)=0 and the coef fi cients c(n,k)and d(n,k)are given by(3.6) and(3.4).Therefore,the degree elevated control pointsin(7.2)are given by

k=0,···,n+1,where P?1=0 and Pn+1=0.

8 The(q,h)-Marsden identity

Theorem 8.1((q,h)-Marsden Identity).The(q,h)-Bernstein polynomials on the interval[a,b] satisfy

where g(t)=qt+h and n ≥ 1.

Proof.To prove(8.1)we use induction with respect to n. First consider the case n=1.By(1.2)and(1.1)we have

In this case the left-hand side of(8.1)is(x ? t),while the right-hand side of(8.1)is

Therefore,(8.1)is true when n=1.

Next assume that(8.1)holds for some n ≥ 1.Set

Then(8.1)takes the form

Now we prove(8.4)for n+1.The left-hand side of(8.4)for n+1 is

with Pn,n+1=0 and Pn,?1=0,provided that we can f i nd en,k=en,k(x)and fn,k=fn,k(x)such that

To simplify the notation we omit some of the variables and parameters in(8.6)and in the equations that follow.From(1.2)and(8.6)we get

where

Equating the constant terms and the t-terms in(8.7),we obtain the system

whereweused(1.1).Addingthesecondequationin(8.9)times g[k](a)tothef i rstequation in(8.9)yields

Therefore

where we used(3.5).Then the second equation in(8.9)and(1.1)yield

From(8.8),(8.10),and(8.11)it follows that

and

Next,by(8.12)and(8.13),we get

We now simplify the last expression in(8.15).We can write

For the coeff i cients A,B,and C in(8.16)using(1.1)we derive

and

From(8.16),(8.17a),(8.17b),and(8.18)we get

Then,from(8.15)and(8.19)it follows that

From(8.14),(8.20),and(8.3)we get

Finally,combining(8.5)and(8.21)we obtain the right-hand side of equation(8.4)for the case n+1.We have shown that(8.4)is true for the case n+1.This completes the proof of the(q,h)-Marsden identity.

9 Future work

Wehaveestablishedseveralimportantproperties,identities,and algorithmsforthe(q,h)-Bernstein polynomials and the(q,h)-B ′ezier curves using only standard mathematical induction.Many of these and other properties have been derived in the recent works[3,4, 8–10].

The most natural next stage of this work is to program and implement the recursive evaluation and degree elevation algorithms for(q,h)-B′ezier curves.Then(q,h)-Bernstein polynomials and(q,h)-B ′ezier surfaces of several variables can be constructed using tensor products of univariate(q,h)-Bernstein polynomials and their analogous properties can be studied.These multivariate(q,h)-Bernstein polynomials can be used as blending functions to def i ne(q,h)-B ′ezier surfaces,and to study their properties and recursive evaluation algorithms.

This future work is outside of the scope of this paper and will be accomplished in future research projects.

[1]G.Farin,Curves and Surfaces for CAGD,5th ed.,Morgan Kaufman,2001.

[2]R.Goldman,Pyramid Algorithms,A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling,The Morgan Kaufman Series in Computer Graphics and Geometric Modeling,Elsevier Science,2003.

[3]R.Goldman and P.Simeonov,Quantum Bernstein basesand quantum B′eziercurves,J.Comput.Appl.Math.,288(2015),284–303.

[4]R.Goldman and P.Simeonov,Formulas andalgorithms forquantum differentiationof quantum Bernstein bases and quantum B′ezier curves based on quantum blossoming,Graphical Models,74(2012),326–334.

[5]N.Gregorz,Approximationpropertiesfor generalizedBernstein polynomials,J.Math.Anal. Appl.,350(2009),50–55.

[6]V.Kac and P.Cheung,Quantum Calculus,Universitext Series,vol.IX,Springer-Verlag,2002.

[7]G.Phillips,Bernstein polynomials based on the q-integers,Annals Numer.Anal.,4(1997), 511–518.

[8]P.Simeonov and R.Goldman,Quantum B-splines,BIT,53(1)(2013),193–223.

[9]P.Simeonov,V.Zaf i ris and R.Goldman,h-Blossoming:A new approach to algorithms and identities for h-Bernstein bases and h-B′ezier curves,Computer Aided Geometric Design,28 (2011),549–565.

[10]P.Simeonov,V.Zaf i ris and R.Goldman,q-Blossoming:A new approach to algorithms and identities for q-Bernstein bases and q-B ′ezier curves,J.Approx.Theory,164(1)(2012),77–104.

Received 17 March 2015;Accepted(in revised version)23 September 2016

?Corresponding author.Email addresses:ilija.jegdic@tsu.edu(I.Jegdi′c),jung sook@yahoo.com (J.Larson),simeonovp@uhd.edu(P.Simeonov)