# The Family of Multiparameter Quaternary Subdivision Schemes

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

---

## Abstract

In the field of subdivision, the smoothness increases as the arity of schemes increases. The family of high arity schemes gives high smoothness comparative to low arity schemes. In this paper, we propose a simple and generalized formula for a family of multiparameter quaternary subdivision schemes. The conditions for convergence of subdivision schemes are also presented. Moreover, we derive subdivision schemes after substituting the different values of parameters. We also analyzed the important properties of the proposed family of subdivision schemes. After comparison with existing schemes, we analyze that the proposed family of subdivision schemes gives better smoothness and approximation compared with the existing subdivision schemes.


---

## Body

## 1. Introduction

Subdivision schemes are the backbone of Computer Aided Geometric Design (CAGD). Subdivision schemes are used for the generation of smooth curves from the initial polygon. If the rules of subdivision schemes are four, then subdivision schemes are called quaternary subdivision schemes.In 2009, a 4-point quaternary scheme is presented in [1]. The purposed scheme has C3-continuity. A family of quaternary schemes is presented in [2]. They used the Cox–De Boor recursion formula for the construction of quaternary schemes. In 2013, Ghaffar et al. [3] presented a generalized formula for the generation of 4-point subdivision schemes of binary, ternary, and quaternary subdivision schemes. In the same year, Amat and Liandrat [4] presented a 4-point scheme for the elimination of the Gibbs phenomenon.In 2018, Pervaz [5] presented a 4-point quaternary scheme. They discuss the shape preserving properties of the subdivision scheme. Ashraf et al. [6, 7] presented and analyzed the geometrical properties of four point interpolating subdivision schemes. Hameed et al. [8] presented a 4-point subdivision scheme for regular curves and surfaces design. Hussain et al. [9] presented a generalized formula for 5-point subdivision schemes of any arity. Khan et al. [10] presented a computational method for the generation of subdivision schemes. Conti and Romani [11] presented an algebraic technique for the generation of m-ary subdivision schemes. Romani [12] presented an algorithm for the generation of dual interpolating m-ary subdivision schemes. Romani and Viscardi [13] presented a new class of univariate stationary interpolating subdivision schemes of arity m. Recently, Mustafa et al. [14] presented a family of integer-point ternary parametric subdivision schemes.


### 1.1. Our Contributions

In the field of subdivision, as arity increases, the smoothness also increases. The main purpose of this work is to present a simple and generalized formula for derivation of multiparametric quaternary subdivision schemes based on Laurent polynomial. The conditions for the construction of subdivision schemes are also presented. Our schemes give better approximation and smoothness compared to the same type of existing subdivision schemes (see Figures1 and 2).Figure 1
(a–c) Comparison of limit curves for close polygons produced by 4-point schemesλ3,3 and α44.
(a)(b)(c)(d)(e)(f)Figure 2
(a–c) Comparison of limit curves for close polygons produced by 4-point schemesλ3,3 and KP.
(a)(b)(c)The paper is organized as follows. In Section2, we present the general formula with different cases of a family of quaternary subdivision schemes. Analysis of the proposed family is presented in Section 3. Section 4 is for the comparison of the proposed family of subdivision schemes with existing subdivision schemes. Conclusions are drawn in Section 5.


## 1.1. Our Contributions

In the field of subdivision, as arity increases, the smoothness also increases. The main purpose of this work is to present a simple and generalized formula for derivation of multiparametric quaternary subdivision schemes based on Laurent polynomial. The conditions for the construction of subdivision schemes are also presented. Our schemes give better approximation and smoothness compared to the same type of existing subdivision schemes (see Figures1 and 2).Figure 1
(a–c) Comparison of limit curves for close polygons produced by 4-point schemesλ3,3 and α44.
(a)(b)(c)(d)(e)(f)Figure 2
(a–c) Comparison of limit curves for close polygons produced by 4-point schemesλ3,3 and KP.
(a)(b)(c)The paper is organized as follows. In Section2, we present the general formula with different cases of a family of quaternary subdivision schemes. Analysis of the proposed family is presented in Section 3. Section 4 is for the comparison of the proposed family of subdivision schemes with existing subdivision schemes. Conclusions are drawn in Section 5.


## 2. General Formula for Multiparameter Family of Quaternary Subdivision Schemes

In this section, we present a general formula for the multiparameter family of quaternary approximating subdivision schemes based on Laurent polynomial. The general formula is(1)λl,qz=1+z+z2+z3l+1a0+a1z+a2z2+⋯+aqzq.The value ofl controls the complexity and that of q controls the parameters in subdivision schemes. By using different values of l and q, we get the Laurent polynomial of family of l+1-point quaternary q+1 parametric subdivision schemes. Here, we will discuss the different cases and conditions for family of quaternary subdivision schemes.Case 1.
By puttingl=2,q=1 and a0+a1=1/16, with a0<1/4,a1<1/4, in (1), we can obtain the Laurent polynomial of subdivision scheme(2)λ2,1z=a1z10+a0+3a1z9+3a0+6a1z8+6a0+10a1z7+10a0+12a1z6+12a0+12a1z5+12a0+10a1z4+10a0+6a1z3+6a0+3a1z2+a1+3a0z+a0.
The mask of the scheme corresponding to the Laurent polynomialλ2,1z is(3)λ2,1=a1,a0+3a1,3a0+6a1,6a0+10a1,10a0+12a1,12a0+12a1,12a0+10a1,10a0+6a1,6a0+3a1,3a0+a1,a0.
The scheme corresponding to mask (3) is(4)P4ik+1=10a0+6a1Pi−1k+6a0+10a1Pik,P4i+1k+1=6a0+3a1Pi−1k+10a0+12a1Pik+a1Pi+1k,P4i+2k+1=3a0+a1Pi−1k+12a0+12a1Pik+a0+3a1Pi+1k,P4i+3k+1=a0Pi−1k+12a0+10a1Pik+3a0+6a1Pi+1k.Case 2.
By settingl=2, q=2 and a0+a1+a2=1/16 with a0<1/4,a1<1/4,a2<1/4 in (2), we get the Laurent polynomial of 3-point scheme(5)λ2,2z=a2z11+a1+3a2z10+a0+3a1+6a2z9+3a0+6a1+10a2z8+6a0+10a1+12a2z7+10a0+12a1+12a2z6+12a0+12a1+10a2z5+12a0+10a1+6a2z4+10a0+6a1+3a2z3+6a0+a2+3a1z2+a1+3a0z+a0.
The mask of the scheme corresponding to the Laurent polynomial (5) is(6)λ2,2=a2,3a2+a1,a0+3a1+6a2,3a0+6a1+10a2,6a0+10a1+12a2,10a0+12a1+12a2,12a0+12a1+10a2,12a0+10a1+6a2,10a0+6a1+3a2,6a0+a2+3a1,a1+3a0,a0.
The scheme corresponding to mask (6) is(7)P4ik+1=10a0+6a1+3a2Pi−1k+6a0+10a1+12a2Pik+a2Pi+1k,P4i+1k+1=6a0+3a1+a2Pi−1k+10a0+12a1+12a2Pik+a1+3a2Pi+1k,P4i+2k+1=3a0+a1Pi−1k+12a0+12a1+10a2Pik+a0+3a1+6a2Pi+1k,P4i+3k+1=a0Pi−1k+6a2+10a1+12a2Pik+3a0+6a1+10a2Pi+1k.Case 3.
By settingl=3, q=2, and a0+a1+a2=1/64, with a0<1/4,a1<1/4,a2<1/4 in (2), we can obtain the Laurent polynomial of 4-point scheme(8)λ3,2z=a2z14+a1+4a2z13+a0+4a1+10a2z12+4a0+10a1+20a2z11+10a0+20a1+31a2z10+20a0+31a1+40a2z9+31a0+40a1+44a2z8+40a0+44a1+40a2z7+44a0+40a1+31a2z6+40a0+20a2+31a1z5+31a0+20a1+10a2z4+20a0+10a1+4a2z3+10a0+4a1+a2z2+4a0+a1z+a0.
The mask of the scheme corresponding to the Laurent polynomial (8) is(9)λ3,2=a2,4a2+a1,a0+4a1+10a2,4a0+10a1+20a2,10a0+20a1+31a2,20a0+31a1+40a2,31a0+40a1+44a2,40a0+44a1+40a2,44a0+40a1+31a2,40a0+20a2+31a1,20a1+31a0+10a2,20a0+10a1+4a2,10a0+4a1+a2,4a0+a1,a0.
The scheme corresponding to mask (9) is(10)P4ik+1=20a0+10a1+4a2Pi−1k+40a0+44a1+40a2Pik+4a0+10a1+20a2Pi+1k,P4i+1k+1=10a0+4a1+a2Pi−1k+44a0+40a1+31a2Pik+10a0+20a1+31a2Pi+1k+a2Pi+2k,P4i+2k+1=4a0+a1Pi−1k+40a0+20a2+31a1Pik+20a0+31a1+40a2Pi+1k+4a2+a1Pi+2k,P4i+3k+1=a0Pi−1k+20a1+31a0+10a2Pik+31a0+40a1+44a2Pi+1k+a0+4a1+10a2Pi+2k.Case 4.
By puttingl=3,q=3, and a0+a1+a2+a3=1/64, with a0<1/4,a1<1/4,a2<1/4,a3<1/4 in (2), we can obtain the Laurent polynomial of 4-point scheme(11)λ3,3z=a3z15+a2+4a3z14+a1+4a2+10a3z13+a0+4a1+10a2+20a3z12+4a0+10a1+20a2+31a3z11+10a0+20a1+31a2+40a3z10+20a0+40a2+44a3+31a1z9+31a0+40a1+44a2+40a3z8+40a0+44a1+40a2+31a3z7+44a0+31a2+40a1+20a3z6+31a1+20a2+10a3+40a0z5+20a1+10a2+4a3+31a0z4+20a0+10a1+4a2+a3z3+4a1+10a0+a2z2+4a0+a1z+a0.
The mask of the scheme corresponding to the Laurent polynomial (11) is(12)λ3,3=a3,4a3+a2,a1+4a2+10a3,a0+4a1+10a2+20a3,4a0+10a1+20a2+31a3,10a0+20a1+31a2+40a3,20a0+31a1+40a2+44a3,31a0+40a1+44a2+40a3,40a0+44a1+40a2+31a3,44a0+40a1+31a2+20a3,40a0+31a1+20a2+10a3,31a0+20a1+10a2+4a3,20a0+10a1+4a2+a3,10a0+4a1+a2,4a0+a1,a0.
The scheme corresponding to the mask is(13)P4ik+1=20a0+10a1+4a2+a3Pi−1k+40a0+44a1+40a2+31a3Pik+4a0+10a1+20a2+31a3Pi+1k+a3Pi+2k,P4i+1k+1=10a0+4a1+a2Pi−1k+44a0+40a1+31a2+20a3Pik+10a0+20a1+31a2+40a3Pi+1k+4a3+a2Pi+2k,P4i+2k+1=4a0+a1Pi−1k+40a0+31a1+20a2+10a3Pik+20a0+31a1+40a2+40a2+44a3Pi+1k+4a2+a1+10a3Pi+2k,P4i+3k+1=a0Pi−1k+31a0+20a1+10a2+4a3Pik+31a0+40a1+44a2+40a3Pi+1k+a0+4a1+10a2+20a3Pi+2k.
Scheme (13) is the general 4-point quaternary scheme with 4 parameters.
Similarly for different values ofl and q, we get the l+1-point quaternary approximating subdivision schemes having q+1 parameters. In Table 1, we present the mask of family members of quaternary schemes for different values of l and q.Table 1
The mask of the unified family of quaternary curve subdivision schemes corresponding to different values ofl and q.
l,qComplexityMask2,13-pointa1,a0+3a1,3a0+6a1,6a0+10a1,10a0+12a1,12a0+12a1,12a0+10a1,10a0+6a1,6a0+3a1,3a0+a1,a0.2,23-pointa2,3a2+a1,a0+3a1+6a2,3a0+6a1+10a2,6a0+10a1+12a2,10a0+12a1+12a2,12a0+12a1+10a2,12a0+10a1+6a2,10a0+6a1+3a2,6a0+a2+3a1,a1+3a0,a0.3,24-pointa2,4a2+a1,a0+4a1+10a2,4a0+10a1+20a2,10a0+20a1+31a2,20a0+31a1+40a2,31a0+40a1+44a2,40a0+44a1+40a2,44a0+40a1+31a2,40a0+20a2+31a1,20a1+31a0+10a2,20a0+10a1+4a2,10a0+4a1+a2,4a0+a1,a0.3,34-pointa3,4a3+a2,a1+4a2+10a3,a0+4a1+10a2+20a3,4a0+10a1+20a2+31a3,10a0+20a1+31a2+40a3,20a0+31a1+40a2+44a3,31a0+40a1+44a2+40a3,40a0+44a1+40a2+31a3,44a0+40a1+31a2+20a3,40a0+31a1+20a2+10a3,31a0+20a1+10a2+4a3,20a0+10a1+4a2+a3,10a0+4a1+a2,4a0+a1,a0.


## 3. Analysis of the Unified Family of Quaternary Curve Subdivision Schemes

This section contains the analysis of important properties of the proposed subdivision schemes. For this, we consider the 4-point scheme. After substituting the values ofa0=w, a1=1/128−w, a2=1/128−w, and a3=w in (13), we get a 4-point parametric scheme(14)P4ik+1=7w+764Pi−1k+2132−13wPik+5w+1564Pi+1k+wPi+2k,P4i+1k+1=5w+5128Pi−1k+71128−7wPik+51128−wPi+1k+3w+1128Pi+2k,P4i+2k+1=3w+1128Pi−1k+51128−wPik+71128−7wPi+1k+5w+5128Pi+2k,P4i+3k+1=wPi−1k+5w+1564Pik+2132−13wPi+1k+7w+764Pi+2k.The Laurent polynomial corresponding to scheme (14) is(15)λz=11281+z+z2+z341+z128w+1−256wz+128wz2,The Laurent polynomial method [15] is used to compute the degree of generation, degree of reproduction, and continuity analysis. Moreover, Rioul’s method [16] is used to compute lower and upper bounds on Hölder regularity of scheme (14). The analysis of other schemes is similar.Theorem 1.
A 4-point quaternary subdivision scheme (14) has cubic reproduction with respect to the dual parametrization for w=−21/1024.Proof.
By taking the derivative of (15) with respect to z, we get(16)λ′z=41+z+z2+z331+2z+3z2w+1128−wz+1128−wz2+wz3+1+z+z2+z341128−w+21128−wz+3wz2,
After substitutingz=1 in (15) and (16), we get λ1=4 and λ′1=30. The value of shift parameter τ=λ′1/4=15/2. Hence, by [15], the subdivision scheme (14) has dual parametrization. Further, we can easily verify that(17)λk1=4∏j=0k−1152−jfork=0,1,2,3withw=−211024,
Hence, by [15], the scheme corresponding to λz has cubic reproduction with respect to the dual parametrization.Table2 summarizes the results of degree of generation, values of parameters, shift parameter, and parametrization of a proposed family of quaternary subdivision schemes. Here, l, q, Dg, values of aq′s, τ, and parametrization denote the positive integer, degree of generation, parameter values, shift parameter, and parametrization of the scheme, respectively.Table 2
The degree of generation of family of unified quaternary curve subdivision scheme for different cases.
Casesl,qDgValues ofaq′sτParametrization1l=2,q=12a0=−3/32, a1=5/327Primala0=5/32, a1=−3/323Primal2l=2,q=22a0=a2=−15/128,a1=19/64112Dual3l=3,q=23a0=a2=−5/128,a1=3/327Primal4l=3,q=33a0=a3=w,a1=a2=1/128−w152DualTheorem 2.
A 4-point quaternary subdivision scheme (14) has C3 continuity for w∈−1/1282/128.Proof.
Consider the Laurent polynomial(18)λ1z=4z31+z+z2+z34λz,where λz is defined in (15). This implies(19)λ1z=4z31+z+z2+z341+z+z2+z34w+1128−wz+1128−wz2+wz3,
After simplification, we get(20)λ1z=256z12w+1128−wz+1128−wz2+wz3.
Letλ1 be the mask of the scheme S1 corresponding to λ1z, then we have(21)λ1=256w,1128−w,1128−w,w,
The scheme corresponding toλz is C3 continuous if 1/4S1∞<1; for this, we have to check that(22)14S1∞=max14256w,2−256w,2−256w,256w.
Ifw∈−1/128,2/128, then 1/4S1∞<1. Then, by [15], the scheme corresponding to λz has C3 continuity, which completes the proof.Theorem 3.
The Hölder regularity of a 4-point scheme (14) is r=4−log4μ, where μ is defined as(23)μ=2−256w,if−1128<w≤1256,μ=256w,if1256<w<2128.Proof.
The Laurent polynomial (15) can be written as(24)λz=1+z+z2+z344bz,where(25)bz=256w+2−256wz+2−256wz2+256wz3.
From (25), the coefficients of z in bz are b0=256w, b1=2−256w, b2=2−256w, and b3=256w. The number of factors in λz is k=4. The matrices Bn has order 3×3 where n=0,1,2 and 3. The elements of the matrices B0,B1,B2, and B3 can be derived by Bnij=b3+n+i−4j, for i, = 1, 2, and 3; then, we have(26)B0=256w002−256w002−256w00,B1=2−256w002−256w00256w00,B2=2−256w00256w000256w0,B3=256w000256w002−256w0.
The eigenvalues ofB0,B1,B2, and B3 are 0,0,256w,0,0,2−256w,0,0,2−256w, and 0,256w,256w, respectively. For bounds on Hölder regularity, we calculate maxρB0,ρB1,ρB2,ρB3≤μ≤maxB0,B1,B2,B3, with . denoting the infinity norm, since μ is bounded from below by the spectral radii and from above by the infinity norm of the matrices B0,B1,B2,B3. So maxρB3,ρB1,ρB2,ρB3=max2−256w,256w and maxB0,B1,B2,B3=max2−256w,256w. Then by [16], we have μ=max2−256w,256w. So Hölder regularity of the scheme S is computed by r=4−log4μ, where μ is defined as(27)μ=2−256wif−1128<w≤1256,μ=256wif1256<w<2128,which completes the proof.Corollary 1.
The 4-point scheme (14) is C3 continuous if and only if 1≤μ<4, i.e., if and only if −1/128<w<2/128.Theorem 4.
The limit stencils providing the evaluations of the basic limit function of the 4-point scheme (14) at integers and half integers are 128w2/15+7w/12+1/5120,31w/5−512w2/15+223/1280,256w2/5−407w/30+1667/2560,31w/5−512w2/15+223/1280,128w2/15+7w/12+1/5120 and 64w/15+1/40,19/40−64w/15,19/40−64w/15,64w/15+1/40, respectively.Proof.
The local subdivision matrices for limit stencils of 4-point scheme (14) at integers and half integers are PIk+1=SIPIk and PI/2k+1=SI/2PI/2k, respectively, with(28)SI=1128+3w51128−w71128−7w5128+5w0w1564+5w2132−13w764+7w00764+7w2132−13w1564+5ww05128+5w71128−7w51128−w1128+3w,PIk+1=P−2k+1P−1k+1P0k+1P1k+1,PIk=P−2kP−1kP0kP1kP2k,(29)SI/2=7w+7642132−13w5w+1564w5w+512871128−7w51128−w3w+11283w+112851128−w71128−7w5w+5128w5w+15642132−13w7w+764,PI/2k+1=P−3/2k+1P−1/2k+1P1/2k+1P3/2k+1andPI/2k=P−3/2kP−1/2kP1/2kP3/2k.
The eigenvalues of the matrixSI/2 are 1/16,1,1/64,1/4. The eigenvectors of local subdivision matrix SI/2 corresponding to eigenvalues are(30)QI/2=11−1−1512w+3512w−571−128w+2384w−9−13512w+3512w−571128w+2384w−9131111.
The inverse ofQI/2 is(31)QI/2−1=1940−64w15−1940+64w15−1940+64w151940−64w15140+64w151940−64w151940−64w15140−64w15−310+64w5910−192w5−910+192w5310−64w5−15−64w5−910+192w5910−192w515+64w5.
For the decomposition of matrixSI/2, we need ΔI/2, where ΔI/2 is the scalar matrix in which eigenvalues are arranged diagonally; therefore, we now compute limk⟶∞ΔI/2k(32)ΔI/2k=116k000010000164k000014kandlimk⟶∞ΔI/2k=0000010000000000.
PI/2k+1=SI/2PI/2k; therefore, PI/2k+1=SI/2kPI/20. This implies(33)P−3/2∞P−1/2∞P1/2∞P3/2∞=140+6415w1940−6415w1940−6415w140+6415w140+6415w1940−6415w1940−6415w140+6415w140+6415w1940−6415w1940−6415w140+6415w140+6415w1940−6415w1940−6415w140+6415wP−3/20P−1/20P1/20P3/20.
Since the subdivision scheme is dual, after computing the limit stencil at half integers by the local matrixSI/2, the limit stencil at integers must be computed as(34)limit stencil integers=limit stencil half integers×SI.
The matrix of limit stencils at half integers is(35)SI/2∞=140+6415w1940−6415w1940−6415w140+6415w140+6415w1940−6415w1940−6415w140+6415w140+6415w1940−6415w1940−6415w140+6415w140+6415w1940−6415w1940−6415w140+6415w.
After multiplying the matrix of limit stencil at half integersSI/2∞ with local subdivision matrix SI, we get(36)SI∞=l1l2l3l4l5l1l2l3l4l5l1l2l3l4l5l1l2l3l4l5,with(37)l1=128w215+7w12+15120,l2=31w5−512w215+2231280,l3=256w25−407w30+16672560,l4=31w5−512w215+2231280,l5=128w215+7w12+15120.
Hence, the limit stencils providing the evaluations of the basic limit functions of the 4-point scheme (14) at integers and half integers are(38)128w2/15+7w/12+1/5120,31w/5−512w2/15+223/1280,256w2/5−407w/30+1667/2560,31w/5−512w2/15+223/1280,128w2/15+7w/12+1/5120,64w/15+1/40,19/40−64w/15,19/40−64w/15,64w/15+1/40respectively, which completes the proof.In Figure3, we present the basic limit functions of the proposed 4-point quaternary 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 3
Basic limit functions produced by the 4-point scheme corresponding to (14) for different values of parameter w. The red lines denote the initial polyline, and the blue, black, and green lines represent the basic limit functions produced with w=−1/256,0,1/256 respectively. The circles denote the evaluations of the basic limit function at integers, and 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 quaternary subdivision schemes with existing quaternary subdivision schemes in visual performance. In Figure1, we present the comparison of proposed 4-point scheme λ3,3 with 4-point scheme α44 presented in [1] a,b&c and 4-point scheme presented in [4] d,e&f, respectively. Here, black dotted lines show the initial polygon, red solid lines are the limit curves of 4-point scheme λ3,3, and blue solid lines are the limit curves of 4-point scheme α44 presented in [1] and 4-point scheme presented in [4]. We see that, our proposed schemes λ3,3 give maximum smoothness and best approximation compared with the schemes presented in [1, 4].In Figure2, we present the comparison of proposed 4-point scheme λ3,3 with 4-point scheme KP presented in [5]. Here, black doted lines show the initial polygon, red solid lines are the limit curve of 4-point scheme λ3,3, and blue solid lines are the limit curve of 4-point scheme KP presented in [5]. We see that the approximating scheme KP presented in [5] gives interpolating behavior, but our proposed schemes λ3,3 give maximum smoothness and best approximation compared with the schemes presented in [5].


## 5. Conclusions

In this paper, we have presented a general formula for the derivation of multiparametric family of quaternary subdivision schemes. We present the complete analysis of the proposed family of the multiparametric quaternary subdivision schemes. We also present the comparison with exiting quaternary subdivision schemes. The comparison shows that our proposed family gives maximum smoothness compared with existing quaternary subdivision schemes.



---

*Source: 4732464-2021-12-14.xml*