# A Family of Integer-Point Ternary Parametric Subdivision Schemes

Authors: Ghulam Mustafa; Muhammad Asghar; Shafqat Ali; Ayesha Afzal; Jia-Bao Liu
Journal: Journal of Mathematics
 (2021)

---

## Abstract

New subdivision schemes are always required for the generation of smooth curves and surfaces. The purpose of this paper is to present a general formula for family of parametric ternary subdivision schemes based on the Laurent polynomial method. The different complexity subdivision schemes are obtained by substituting the different values of the parameter. The important properties of the proposed family of subdivision schemes are also presented. The continuity of the proposed family isC2m. Comparison shows that the proposed family of subdivision schemes has higher degree of polynomial generation, degree of polynomial reproduction, and continuity compared with the exiting subdivision schemes. Maple software is used for mathematical calculations and plotting of graphs.


---

## Body

## 1. Introduction

Computer aided geometric design (CAGD) is a field which is related to computational mathematics. Subdivision schemes are the important tool of CAGD. Subdivision schemes are used for the generation of smooth curves from initial polygon. In the field of subdivision, the subdivision schemes having three rules are called ternary subdivision schemes. To improve the flexibility of subdivision schemes, some parameters are used in subdivision schemes. Here, we present a brief survey of the parametric ternary subdivision schemes.In 2002, Hassan et al. [1] purposed a family of interpolating 3-point ternary subdivision schemes with C1-continuity. They also compare with binary subdivision schemes. Wang and Qin [2] proposed an improved ternary interpolating subdivision scheme. They also discussed the parameterizations and manipulate the split joint problem with interpolating ternary subdivision scheme. Ko et al. [3] derived a 4-point ternary scheme from cubic polynomial interpolation which has smaller support and higher smoothness, comparing to binary 4-point and 6-point schemes and ternary 3-point and 4-point schemes.Mustafa and Ashraf [4] presented and analyzed the 6-point ternary scheme with the parameter. The proposed scheme has C2 continuous over the parametric interval. Mustafa et al. [5] described the general formula for odd-point parametric ternary subdivision schemes. They proved that the cubic B-spline scheme was a particular case of the suggested ternary scheme. They also demonstrated the effect of the parameter on the limit curve. Pan et al. [6] derived the relation between combined approximating and interpolating subdivision scheme. The resulting curve from the combined subdivision scheme was C2 continuous, when analyzed by Laurent polynomial. Siddiqi et al. [7–9] introduced a family of ternary interpolatory and approximating subdivision scheme with one parameter. It was used to generate fractal curves and surfaces. They also presented an algorithm which produced ternary m-point approximating subdivision schemes by taking m as integer greater than 2 with the help of uniform B-spline blending functions.Rehan and Siddiqi [10] presented a family of 3-point and 4-point ternary approximating subdivision schemes. They also analyzed degree of smoothness of a family of ternary 3-point and 4-point subdivision schemes which are C1 and C3 continuity, respectively. Ashraf et al. [11, 12] presented and analyzed the geometrical properties of the 4-point ternary interpolating subdivision scheme. This scheme involves a tension parameter. They derived the conditions on the tension parameter and initial control polygon that permitted the creation of positivity and monotonicity-preserving curves after a finite number of subdivision steps.In 2021, Tan and Tong [13] presented a nonstationary 4-point ternary interpolating subdivision scheme. They also discussed the shape preserving properties of the proposed subdivision scheme. Tariq et al. [14] presented a unified class of combined subdivision schemes with two-shape control parameters in order to grow versatility for overseeing valuable necessities. Hameed et al. [15] presented a new method to construct a family of 2N+2-point binary subdivision schemes with one tension parameter. Mustafa et al. [16] presented a subdivision collocation method to resolve Bratu’s boundary value problem by using the approximating subdivision scheme.


### 1.1. Our Contributions

The main purpose of this work is to present a generalized formula for derivation of parametric ternary subdivision schemes. Our proposed high complexity schemes have high values of continuity, degree of generation, and degree of reproduction of polynomials. The claim is proved in comparison section (see Table1). Our schemes give better approximation and smoothness when compared with the same type of exiting subdivision schemes (see Figure 1).Table 1
The comparison of a family of ternary schemesSm, where Cs, C, and Gd are complexity, continuity analysis, and generation degree of subdivision schemes, respectively.
CsSchemesTypeCGd3-pointA1 schemeApproxC2 for w∈−3/36,9/36Quadratic3-pointScheme [17]ApproxC1 for w∈0,1/2Linear3-pointScheme [1]IntC1Linear3-pointScheme [18]ApproxC2Quadratic3-pointScheme [10]ApproxC1Linear3-pointScheme [5]ApproxC2 for w∈−1/12,11/2—3-pointScheme [9]ApproxC2—5-pointA2 schemeApproxC4 for w∈−3/36,9/36Quartic5-pointScheme [17]ApproxC4 for w∈0,1/2Quartic5-pointScheme [18]IntC1Linear5-pointScheme [5]ApproxC3 for μ∈53/8748,187/17496Cubic5-pointScheme [9]ApproxC4—6-pointA3 schemeApproxC6 for w∈−3/36,9/36Sextic6-pointScheme [4]IntC2Linear6-pointScheme [9]ApproxC5QuadraticFigure 1
(a–d) Comparison of limit curves for close polygons produced by 3-point schemesS03, S1, and G3.
(a)(b)(c)(d)The paper is organized as follows. In Section2, we present the general formula and derivations of family of ternary subdivision schemes. Analysis of the proposed family is presented in Section 3. Section 4 is for comparison of proposed family of subdivision schemes with exiting subdivision schemes. Conclusions are drawn in Sections 5.


## 1.1. Our Contributions

The main purpose of this work is to present a generalized formula for derivation of parametric ternary subdivision schemes. Our proposed high complexity schemes have high values of continuity, degree of generation, and degree of reproduction of polynomials. The claim is proved in comparison section (see Table1). Our schemes give better approximation and smoothness when compared with the same type of exiting subdivision schemes (see Figure 1).Table 1
The comparison of a family of ternary schemesSm, where Cs, C, and Gd are complexity, continuity analysis, and generation degree of subdivision schemes, respectively.
CsSchemesTypeCGd3-pointA1 schemeApproxC2 for w∈−3/36,9/36Quadratic3-pointScheme [17]ApproxC1 for w∈0,1/2Linear3-pointScheme [1]IntC1Linear3-pointScheme [18]ApproxC2Quadratic3-pointScheme [10]ApproxC1Linear3-pointScheme [5]ApproxC2 for w∈−1/12,11/2—3-pointScheme [9]ApproxC2—5-pointA2 schemeApproxC4 for w∈−3/36,9/36Quartic5-pointScheme [17]ApproxC4 for w∈0,1/2Quartic5-pointScheme [18]IntC1Linear5-pointScheme [5]ApproxC3 for μ∈53/8748,187/17496Cubic5-pointScheme [9]ApproxC4—6-pointA3 schemeApproxC6 for w∈−3/36,9/36Sextic6-pointScheme [4]IntC2Linear6-pointScheme [9]ApproxC5QuadraticFigure 1
(a–d) Comparison of limit curves for close polygons produced by 3-point schemesS03, S1, and G3.
(a)(b)(c)(d)The paper is organized as follows. In Section2, we present the general formula and derivations of family of ternary subdivision schemes. Analysis of the proposed family is presented in Section 3. Section 4 is for comparison of proposed family of subdivision schemes with exiting subdivision schemes. Conclusions are drawn in Sections 5.


## 2. A Family of Integer-Point Ternary Schemes

In this section, we propose a general formula for integer-point ternary approximating subdivision schemes with one parameter in the form of Laurent polynomial:(1)Amz=132m−11+z+z22m+1112+w+16−2wz+112+wz2,where m=0,1,2, and 3. By putting m=0 in (1), we get the Laurent polynomial of a 2-point interpolating subdivision scheme:(2)A0z=14+3w+34−3wz+z2+34−3wz3+14+3wz4.The scheme corresponding to the Laurent polynomial (2) is(3)f3ik+1=fik,f3i+1k+1=34−3wfik+14+3wfi+1k,f3i+2k+1=14+3wfik+34−3wfi+1k.By puttingm=1 in (1), we get the Laurent polynomial of a 3-point approximating subdivision scheme:(4)A1z=136+13w+536+13wz+1336+13wz2+1118−23wz3+1318−23wz4+1118−23wz5+1336+13wz6+536+13wz7+136+13wz8.The scheme corresponding to the Laurent polynomial (4) is(5)f3ik+1=1336+13wfi−1k+1118−23wfik+136+13wfi+1k,f3i+1k+1=536+13wfi−1k+1318−23wfik+536+13wfi+1k,f3i+2k+1=136+13wfi−1k+1118−23wfik+1336+13wfi+1k.By puttingm=2 in (1), we get the Laurent polynomial of a 5-point approximating subdivision scheme:(6)A2z=1324+127w+7324+19wz+13162+29wz2+65324+527wz3+1027z4+1936−13wz5+1627−49wz6+1936−13wz7+1027z8+65324+527wz9+13162+29wz10+7324+19wz11+1324+127wz12.The scheme corresponding to the Laurent polynomial (6) is(7)f3ik+1=13162+29wfi−2k+1936−13wfi−1k+1027fik+7324+19wfi+1k,f3i+1k+1=7324+19wfi−2k+1027fi−1k+1936−13wfik+13162+29wfi+1k,f3i+2k+1=1324+127wfi−2k+65324+527wfi−1k+1627−49wfik+65324+527wfi+1k+1324+127wfi+2k.By puttingm=3 in (1), we get the Laurent polynomial of a 6-point approximating subdivision scheme:(8)A3z=12916+1243w+1324+5243wz+432916+581wz2+35729+28243wz3+3432916+35243wz4+6652916+781wz5+175486−14243wz6+13732916−55243wz7+125243−827wz8+13732916−55243wz9+175486−14243wz10+6652916+781wz11+3432916+35243wz12+35729+28243wz13+432916+581wz14+1324+5243wz15+12916+1243wz16.The scheme corresponding to the Laurent polynomial (8) is(9)f3ik+1=432916+581wfi−2k+6652916+781wfi−1k+125243−827wfik+6652916+781wfi+1k+432916+581wfi+2k,f3i+1k+1=1324+5243wfi−2k+3432916+35243wfi−1k+13732916−55243wfik+175486−14243wfi+1k+35729+28243wfi+2k+12916+1243wfi+3k,f3i+2k+1=12916+1243wfi−2k+35729+28243wfi−1k+175486−14243wfik+13732916−55243wfi+1k+3432916+35243wfi+2k+1324+5243wfi+3k.Similarly by substituting the different values ofm, we get the family members of ternary subdivision schemes. Table 2 contains the mask of proposed family members of ternary subdivision schemes corresponding to m=0,1,2, and 3.Table 2
The mask of integer-point ternary subdivision schemesAm corresponding to the different values of m.
mMask0A0=1/4+3w,3/4−3w,1,3/4−3w,1/4+3w1A1=1/36+1/3w,5/36+1/3w,13/36+1/3w,11/18−2/3w,13/18−2/3w,11/18−2/3w, 13/36+1/3w,5/36+1/3w,1/36+1/3w2A2=1/324+1/27w,7/324+1/9w,13/162+2/9w,65/324+5/27w,10/27,19/36−1/3w,16/27−4/9w,19/36−1/3w,10/27,65/324+5/27w,13/162+2/9w,7/324+1/9w,1/324+1/27w3A3=1/2916+1/243w,1/324+5/243w,43/2916+5/81w,35/729+28/243w,343/2916+35/243w, 665/2916+7/81w,175/486−14/243w,1373/2916−55/243w,125/243−8/27w,1373/2916−55/243w,175/486−14/243w,665/2916+7/81w,343/2916+35/243w,35/729+28/243w,43/2916+5/81w,1/324+5/243w,1/2916+1/243w


## 3. Analysis of Integer-Point Ternary Schemes

This section contains analysis of important properties of proposed subdivision schemes. Laurent polynomial [19] is used to compute the degree of generation, degree of reproduction, and continuity analysis. While Rioul’s method [20] is used to compute lower and upper bounds on Hölder regularity of the scheme corresponding to Amz.Theorem 1.
Whenever convergent and generating cubic polynomials, the family of ternary subdivision schemes (1) has cubic degree of reproduction with respect to the primal parametrization.Proof.
By taking the derivative of (1) with respect to z, we obtain(10)Am′z=132m−11+z+z21+z+z22m+12m+11+2z112+w+16−2wz+112+wz2+132m−11+z+z22m+116−2w+16+wz.
After substitutingz=1 in (4) and (10, we get Am1=3 and Am′1=6m+6. After taking the first three derivatives of (10) and substituting z=1, we have(11)Am″1=12m2+22m+192+18w,Am′″1=24m3+60m2+45m+212+108mw+54w.
The value of shift parameterτ=Am′1/3=2m+2. Hence, by [19], the subdivision schemes corresponding to (1) have primal parametrization. Furthermore, for different values of m, we can easily verify that(12)Amk1=3∏j=0k−12m+2−jfor allk=1,2,3.
Hence, by [19], the schemes corresponding to Amz have cubic degree of reproduction with respect to the primal parametrization.Table3 summarizes the results of degree of generations, shift parameter, degree of reproductions, and parametrization of proposed family of integer-point ternary subdivision schemes. Here, m, Gd, τ, and Rd and parametrization denote the positive integer, degree of generation, shift parameter, degree of reproduction, and parametrization of the scheme, respectively.Table 3
The degree of generation and degree of reproduction w.r.t parameterization for different values ofm.
mGdτRdParameterization124Quadratic, whenw=−5/12Primal246Cubic, whenw=−23/36Primal368Cubic, whenw=−31/36PrimalTheorem 2.
The family of ternary approximating subdivision schemes (1) has C2m continuity when w∈−3/36,9/36.Proof.
ForC2m continuity of the schemes corresponding to Amz, consider the Laurent polynomial:(13)Am1z=3z21+z+z22m+1Amz,where Amz is defined in (1). This implies(14)Am1z=3z21+z+z22m+1132m−11+z+z22m+1112+w+16−2wz+112+wz2.
After simplification, we obtain(15)Am1z=9z4m+2112+w+16−2wz+112+wz2.
LetAm1 be the mask of the scheme Sm corresponding to Am1z; then, we have(16)Am1=912+9w,96−18w,912+9w.
The scheme corresponding toAm1z is C2m continuous if 1/3Sm∞<1, for this, we have to check that(17)13Sm∞=max936+3w,918−6w,936+3w<1.
1/3Sm∞<1 when w∈−3/36,9/36. The schemes corresponding to Amz has C2m continuity which completes the proof.Theorem 3.
The Hölder regularity of a family of schemesSm corresponding to (1) is r=2m+1−log3μ, where μ is defined as(18)μ=32−18w,if−336<w≤136,μ=34+9wif136<w<936.Proof.
The Laurent polynomial (1) can be written as(19)Amz=1+z+z232m+1bmz,where(20)bmz=34+9w+96−18wz+34+9wz2.
From (20), the coefficients of z in bz are b0=3/4+9w, b1=9/6−18w, and b2=3/4+9w. The number of factors in Amz are k=2m+1. The matrices Bn of order 2×2, where n=0,1,2 and the elements of the matrices B0,B1, and B2 can be derived by Bnij=b2+n+i−3j, for i, j = 1 and 2, we have(21)B0=34+9w064−18w0,B1=64−18w034+9w1,&B2=34+9w0034+9w.
The eigenvalues ofB0,B1, and B2 are 0,3/4+9w,0,3/2−18w, and 3/4+9w,3/4+9w, respectively. For bounds on Hölder regularity, we calculate maxρB0,ρB1,ρB2≤μ≤maxB0,B1,B2, with ⋅ denoting the infinity norm since μ is bounded from below by the spectral radii and from above by the infinity norm of the metrics B0,B1,andB2. So, maxρB0,ρB1,ρB2=max3/4+9w,3/2−18w and maxB0,B1,B2=max3/2−18w,3/4+9w. Then, by [20], we have μ=max3/2−18w,3/4+9w. So, Hölder regularity of the scheme Sm is computed by r=2m+1−log3μ, where μ is defined as(22)μ=32−18wif−336<w≤136,μ=34+9wif136<w<936,which completes the proof.Corollary 1.
The family of schemesSm corresponding to (1) is C2m continuous if and only if 1≤μ<3, i.e., if and only if −3/36<w<9/36.Theorem 4.
The limit stencils providing the evaluations of the basic limit function of the 3-point scheme (5) at integers and half integers are(23)3w8+532,1116−3w4,3w8+532,3w16+164,3164−3w16,3164−3w16,3w16+164,respectively.Proof.
The local subdivision matrices for limit stencils of 3-point scheme (5) at integers and half integers are fIk+1=SIfIk and fI/2k+1=SI/2fI/2k, respectively, where(24)SI=w3+13361118−2w3w3+136w3+5361318−2w3w3+536w3+1361118−2w3w3+1336,fIk+1=f−1k+1f0k+1f1k+1,fIk=f−1kf0kf1k,SI/2=w3+5361318−2w3w3+5360w3+1361118−2w3w3+133600w3+13361118−2w3w3+1360w3+5361318−2w3w3+536,fI/2k+1=f−3/2k+1f−1/2k+1f1/2k+1f3/2k+1,fI/2k=f−3/2kf−1/2kf1/2kf3/2k.
The eigenvalues of the matricesSI and SI/2 are 1,1/9,1/3 and 1/3,1,1/9,−2w/3+1/18, respectively. The eigenvectors of local subdivision matrices SI and SI/2 corresponding to eigenvalues are(25)QI=11−1112w+512w−110111,QI/2=−111−1−13112w+112w−31−12w+112w−713112w+112w−3112w+112w−71111.
The inverse ofQI and QI/2 are(26)QI−1=3w8+5321116−3w43w8+5321132−3w8−1116+3w41132−3w8−12012,QI/2−1=−312w+1412w+5312w−7412w+5−312w−7412w+5312w+1412w+53w16+1643164−3w163164−3w163w16+1643164−3w16−3164+3w16−3164+3w163164−3w1612w−7412w+5−312w−7412w+5312w−7412w+5−12w−7412w+5.
For the decomposition of matricesSI and SI/2, we need ΔI and ΔI/2, respectively, where ΔI and ΔI/2 are the scalar matrices in which eigenvalues are arranged diagonally. Therefore, now compute limk⟶∞ΔIk and limk⟶∞ΔI/2k:(27)ΔIk=100019k00013k,ΔI/2k=13k00001000019k0000−2w3+118k.
This implies(28)limK⟶∞ΔIk=100000000,limK⟶∞ΔI/2k=0000010000000000.
SincefIk+1=SIfIk, therefore, fIk+1=SIkfI0. This implies(29)f−1∞f0∞f1∞=3w8+5321116−3w43w8+5323w8+5321116−3w43w8+5323w8+5321116−3w43w8+532f−10f00f10.
Similarly,fI/2k+1=SI/2fI/2k. Therefore, fI/2k+1=SI/2kfI/20. This implies(30)f−3/2∞f−1/2∞f1/2∞f3/2∞=3w16+1643164−3w163164−3w163w16+1643w16+1643164−3w163164−3w163w16+1643w16+1643164−3w163164−3w163w16+1643w16+1643164−3w163164−3w16s3w16+164f−3/20f−1/20f1/20f3/20.
Hence, the limit stencils providing the evaluations of the basic limit function of the 3-point scheme (5) at integers and half integers are 3w/8+5/32,11/16−3w/4,3w/8+5/32 and 3w/16+1/64,31/64−3w/16,31/64−3w/16,3w/16+1/64, respectively, which completes the proof.
In Figure2, we present the basic limit function of the proposed 3-point ternary approximating subdivision scheme for different values of w and show its evaluations at integers and half integers which coincide with the limit stencils computed in Theorem 4.Figure 2
Basic limit functions produced by the 3-point scheme corresponding toS1 for different values of parameter w. The red line denotes the initial polyline and the blue, black, and green lines represent the basic limit function produced with w=−1/12,0,3/12, respectively. The circles denote the evaluations of the basic limit function at integers; the asterisks denote the evaluations of the basic limit function at half integers.


## 4. Comparison with Existing Schemes

Here, we will present the comparison of our proposed family of ternary subdivision schemes with existing ternary subdivision schemes in the form of theoretical properties and visual performances. In Table1, we present comparison of same complexity subdivision schemes. From Table 1, we see that our proposed family of ternary subdivision schemes has higher continuity, degree of generation, and degree of reproduction compared with the existing subdivision schemes.In Figure3, we present some visual performances of proposed 3-point ternary approximating subdivision scheme. In Figure 1, we present the comparison of the proposed 3-point scheme S1 with 3-point scheme G3 presented in [5] and 3-point scheme S03 presented in [17]. Here, black dotted lines show the initial polygon, red solid lines are the limit curve of 3-point scheme S03 presented in [17], and blue solid lines are the limit curve of 3-point scheme G3 presented in [5]. Mathematically, the continuity of all 3-point schemes is the same, which is C2 continuity.Figure 3
(a–d) Limit curves for close polygons produced by the scheme corresponding toS1.
(a)(b)(c)(d)


## 5. Conclusions

In this paper, we presented a general formula for derivation of parametric family of ternary subdivision schemes. We presented the complete analysis of the proposed family of parametric ternary subdivision schemes. We also presented the comparison with exiting ternary subdivision schemes. Comparison shows that our proposed family has high continuity, degree of generation and reproduction compared with the same type exiting subdivision schemes. From Table1, we observed that our proposed 3-point and 5-point schemes have C2 and C4 continuity, respectively, which are similar to the schemes presented in [1, 5, 9, 10, 17, 18]. Our 6-point scheme has C6 continuity which is greater than the 6-point schemes presented in [4, 9]. Similarly, the generation degree of our proposed schemes is also higher than the exiting schemes.



---

*Source: 9281006-2021-10-14.xml*