# Variations in 2D and 3D Models by a New Family of Subdivision Schemes and Algorithms for its Analysis

Authors: Rabia Hameed; Ghulam Mustafa; Rizwan Majeed
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

A new family of combined subdivision schemes with one tension parameter is proposed by the interpolatory and approximating subdivision schemes. The displacement vectors between the points of interpolatory and approximating subdivision schemes provide the flexibility in designing the limit curves and surfaces. Therefore, the limit curves generated by the proposed subdivision schemes variate in between or around the approximating and interpolatory curves. We also design few analytical algorithms to study the properties of the proposed schemes theoretically. The efficiency of these algorithms is analyzed by calculating their time complexity. The graphical representations and graphical properties of the proposed schemes are also analyzed.


---

## Body

## 1. Introduction

A common problem in computer aided geometric design consists of drawing smooth curves and surfaces that either interpolate or approximate a given shape. Subdivision schemes are one of the most successful approaches in this area. Subdivision schemes are used to construct smooth curves and surfaces from a given set of control points through iterative refinements. Due to its clarity and simplicity, subdivision schemes have been esteemed in many fields such as image processing, computer graphics, and computer animation. Generally, subdivision schemes can be categorized as interpolatory and approximating subdivision schemes. Interpolatory schemes get better shape control while approximating schemes have better smoothness. The most important interpolatory 4-point binary subdivision scheme was proposed by Dyn et al. [1] which gives the curves with C1 continuity. This scheme was extended to the 6-point binary interpolatory scheme by Weissman [2]. The 6-point scheme presented by Weissman [2] gives the limiting curves with C2 continuity. Most of the approximating schemes were developed from splines. Two of the most famous approximating schemes are Chaikin’s subdivision scheme [3] and cubic B-spline subdivision scheme [4], which actually generate uniform quadratic and cubic B-spline curves with C1 continuity and C2 continuity, respectively. There also exists a class of parametric subdivision schemes, called combined subdivision schemes. Combined subdivision schemes can be regarded either as a member of the approximating schemes or of the interpolatory schemes according to the specific values assumed by the parameters. Pan et al. [5] presented a combined ternary 3-point relaxed subdivision scheme with three tension parameters. Novara and Romani [6] extended their technique to construct a 3-point relaxed ternary combined subdivision scheme with three tension parameters to generate curves up to C3 continuity. Recently, Zhang et al. [7] also used similar technique to construct a 4-point relaxed ternary scheme with four tension parameters to generate the curves up to C4 smoothness. The nice performance of combined subdivision schemes motivates us to the direction of constructing the binary combined subdivision scheme. Our contribution in this manner is presented in this research.The remainder of this article is organized as follows: Section2 deals with some basic definition and basic results. Section 3 provides the framework for constructing a family of combined binary subdivision schemes. In Section 4, we provide the analytical properties of the proposed family of schemes. Section 5 gives the graphical behaviors and graphical properties of the proposed family of schemes. Concluding remarks are presented in Section 6.


## 2. Preliminaries

In this section, we present some basic notations and definition relating to the results which we have used in this article.A general compact form of linear, uniform, and stationary binary univariate subdivision schemeSa which maps a polygon Pk=Pik,i∈ℤ to a refined polygon Pk+1=Pik+1,i∈ℤ is defined as(1)Pik+1=∑j∈ℤai−2jPjk,i∈ℤ.The symbol of the above subdivision scheme is given by the Laurent polynomial(2)az=∑i∈ℤaizi,z∈ℂ∖0,where a=ai,i∈ℤ is called the mask of the subdivision scheme. The necessary condition for the binary subdivision scheme (1) to be convergent is that its mask satisfies the basic sum rule(3)∑j∈ℤai−2j=1,i=0,1,which is equivalent to the following relation:(4)a−1=2and,a−1=0.Definition 1.
An algorithm is a procedure for solving a mathematical problem in a finite number of steps that frequently involves repetition of an operation.Definition 2.
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. It is denoted byTn, where n is the input of the given algorithm. The time complexity indicates the number of times the operations are executed in an algorithm. The number of instructions executed by a program is affected by the size of the input and how their elements are arranged.Definition 3.
Step count method considers each and every step to the given algorithm for calculating the final time complexity of the given algorithm. So, each and every step in the given algorithm contributes to the final complexity of given algorithm.Definition 4.
Worst-case time complexity denotes the longest running timeOn of an algorithm given any input of size n. It gives an upper bound on time requirements.Definition 5.
Best-case time complexity denotes the shortest running timeΩn of an algorithm given any input of size n. It gives a lower bound on time requirements.


## 3. Family of the Combined Primal Schemes

In this section, we discuss the construction of the family of2n+2-point binary relaxed schemes. These schemes are the binary schemes, so are the combination of two refinement rules. One of these rules, consists of the affine combination of 2n+1-point of level k to insert a new point at level k+1, is used to update the vertex of the given polygon; hence, it is called the vertex rule. The other refinement rule, consists of the affine combination of 2n+2-points of level k to insert a new point at level k+1, is used for subdividing each edge of the given polygon and so is called the edge rule. Before going to the construction process of the family of combined subdivision schemes, we discuss our motivation behind this research here.


### 3.1. Motivation and Contribution

In this article, we define a novel technique for constructing combined subdivision schemes by using interpolatory and approximating subdivision schemes with optimal performance in curves and surface fitting. Since the family of interpolatory schemes by Deslauriers and Dubuc [8] gives optimal performance in reproducing polynomials and the family of approximating B-spline schemes gives good performance in fitting curves with higher continuity, so we are motivated to unify them into a single family of schemes.The2n+2-point interpolatory subdivision schemes defined by Deslauriers and Dubuc [8] can reproduce polynomials up to degree 2n+1 and generate the limiting curves with C1. Whereas, the 2n+2-point relaxed B-spline approximating schemes are C4n-continuous, while the degree of polynomial reproduction of these schemes is only one. Since the discussed two schemes are the primal schemes, hence each of them is the combination of one vertex and one edge rules. The vertex rule of interpolatory schemes keeps the initial vertices at every level of subdivision, while the vertex rule of the approximating schemes updates the initial vertices at each level of subdivision. Similarly, the edge rule of each scheme subdivides every edge of the given polygon into two edges at each level of subdivision. The limit curves generated by the interpolatory and approximating schemes after 4 subdivision levels are shown in Figure 1. In this article, we construct a family of combined subdivision schemes with one parameter which controls the shape of the limit curve.Figure 1
Red bullets and red lines represent initial points and initial polygon, respectively. Blue bullets and blue curve are the points and limiting curve generated by the 4-point scheme by Deslauriers and Dubuc [8], respectively, after 4 subdivision levels. Whereas black bullets and black curve are the points and limiting curve generated by the 4-point relaxed B-spline scheme, respectively, after 4 subdivision levels.We construct the new family of schemes by the family of interpolatory schemes defined by Deslauriers and Dubuc [8] and the family of approximating B-spline schemes. Therefore, the proposed family of schemes carry the properties of these two types of schemes and give optimal numerical and mathematical results. From Figure 2. Figure 3, we can see the better performance of the proposed schemes than that of their parent schemes (schemes which are used in their construction). Figure 2 shows that if we choose the value of tension parameter for the proposed 4-point scheme between −2.5 and −2, then this scheme is good for fitting noisy data. Figure 3(c) shows that the curves fitted by the proposed 6-point scheme do not give the artifacts as presented by the 6-point scheme [8] in Figure 3(a). This figure also shows that the curve fitted by the proposed scheme preserve the shape of the initial polygon if we take value of tension parameter between −0.5 and 0, while the curve fitted by the 6-point B-spline scheme does not have this ability, as shown in Figure 3(b).Figure 2
Black bullets are the initial points, whereas the solid lines show the limit curves generated by the binary primal schemes. (a) 4-point interpolatory scheme, (b) 4-point B-spline scheme,and (c) proposed 4-point scheme forα=−2.5.
(a)(b)(c)Figure 3
Dotted lines and black bullets are the initial polygons and initial points, respectively. Whereas the solid lines show the limit curves generated by the binary primal schemes. (a) 6-point interpolatory scheme, (b) 6-point B-spline scheme, and (c) proposed 6-point scheme forα=−0.32.
(a)(b)(c)Construction of the family of schemes is discussed in coming subsections in detail.


### 3.2. Framework for the Construction of Family of Subdivision Schemes

The family of2n+2-point interpolatory subdivision schemes, constructed by Lagrange’s interpolatory polynomials presented by Deslauriers and Dubuc [8], is defined by two subdivision rules. The vertex rule is R2i,2n+2k+1=Pi,2n+2k, and the edge rule is(5)R2i+1,2n+2k+1=124n+1∑j=−n−1n−1jn+12j+12n+1n2n+1n+j+1Pi+j+1,2n+2k.The refinement rules of the family of2n+2-point relaxed approximating schemes, i.e. degree-4n+1 binary B-spline subdivision schemes, are(6)Q2i,2n+2k+1=124n+1∑j=02n4n+22j+1Pi+j−n,2n+2k,Q2i+1,2n+2k+1=124n+1∑j=02n+14n+22jPi+j−n,2n+2k,where n∈ℤ+. Let us denote the displacement vectors from the degree-4n+1 B-spline refinement points Q2i,2n+2k+1&Q2i+1,2n+2k+1 to the refinement points R2i,2n+2k+1&R2i+1,2n+2k+1 of 2n+2-point interpolatory subdivision scheme defined in (5) after one step of refinements by D2i,2n+2k+1&D2i+1,2n+2k+1, respectively. Hence, the displacement vectors are(7)D2i,2n+2k+1=R2i,2n+2k+1−Q2i,2n+2k+1,D2i+1,2n+2k+1=R2i+1,2n+2k+1−Q2i+1,2n+2k+1.Now, a new family of primal combined2n+2-point subdivision schemes can be obtained by translating the points R2i,2n+2k+1&R2i+1,2n+2k+1, that are provided by the binary interpolatory subdivision schemes (5) to the new position according to the displacement vectors αD2i,2n+2k+1&αD2i+1,2n+2k+1, respectively.(8)P2i,2n+2k+1=R2i,2n+2k+1+αD2i,2n+2k+1,P2i+1,2n+2k+1=R2i+1,2n+2k+1+αD2i+1,2n+2k+1,which can be further written as(9)P2i,2n+2k+1=−α24n+1∑j=0,j≠n2n4n+22j+1Pi+j−n,2n+2k+124n+124n+11+α−α×4n+22n+1Pi,2n+2k,P2i+1,2n+2k+1=124n+1∑j=02n+1−1j−n−1n+12j−2n−12n+1n2n+1j+α−1j−n−1n+12j−2n−1×2n+1n2n+1j−4n+22jPi+j−n,2n+2k.The rules defined in (9) are the refinement rules of the proposed family of 2n+2-point combined schemes, which are equivalent to the following general form:(10)P2i,2n+2k+1=∑j=02na2j+1,2n+2Pi+j−n,2n+2k,P2i+1,2n+2k+1=∑j=02n+1a2j,2n+2Pi+j−n,2n+2k.The mask symbol of the above scheme is(11)a2n+2z=∑j=04n+2aj,2n+2zj=1+z2n+222n+1A2n+2z,with(12)A2n+2z=∑j=02nAj,2n+2zj,where aj,2n+2:j=0,1,…,4n+2 and Aj,2n+2:j=0,1,…,2n are the coefficients of zj:j=0,1,…,4n+2 and zj:j=0,1,…,2n, respectively in (11) and (12).Remark 1.
Ifα⟶0, the family of proposed 2n+2-point schemes converges to the family of 2n+2-point interpolatory schemes proposed in [8]. Whereas if α⟶−1, the family of proposed 2n+2-point schemes converges to the family of 2n+2-point relaxed approximating B-spline schemes of degree-4n+1.


### 3.3. The Geometrical and Mathematical Interpretation of the Family of Schemes

The family of proposed schemes (9) is obtained by moving the points R2i,2n+2k+1 and R2i+1,2n+2k+1 of the family of schemes (5) to the new position according to the displacement vectors αD2i,2n+2k+1 and αD2i+1,2n+2k+1, respectively. In order to make the construction of the family of schemes understandable, we explain the following steps by fixing n=1 and k=0.Figure 4
Geometrical construction of the scheme fork=0 and n=1.Step 1.
We take the pointsPi−2,40=Pi−2k, Pi−1,40=Pi−1k, Pi,40=Pik, Pi+1,40=Pi+1k, Pi+2,40=Pi+2k, Pi+3,40=Pi+3k, Pi+4,40=Pi+4k, and Pi+5,40=Pi+5k as the initial control points, i.e. at zeroth level of subdivision. The points are shown by red bullets in Figure 4. In this figure, the combination of red lines makes the initial polygon.Step 2.
Now, we calculate pointsR2ik+1 and R2i+1k+1 which are denoted by blue solid squares in Figure 4. We calculate fifteen points (blue solid squares) by applying the following refinement rules of the 4-point interpolatory scheme of Deslauriers and Dubuc [8] on the initial points(13)R2ik+1=R2i,4k+1=Pik,R2i+1k+1=R2i+1,4k+1=−116Pi−1k+916Pik+916Pi+1k−116Pi+2k.
All the points inserted by the above subdivision scheme are shown in Figure4; however, we restrict our next calculations to only two points R2ik+1 and R2i+1k+1. In this figure, blue polygon is the initial polygon obtained from the scheme (13).Step 3.
In this step, we calculate and restrict next calculations to only the pointsQ2ik+1 and Q2i+1k+1 denoted by black solid squares. Again, the fifteen points, denoted by black solid squares in Figure 4, are calculated by the refinement rules of the 4-point relaxed binary B-spline scheme of degree-5 which is defined as follows:(14)Q2ik+1=Q2i,4k+1=316Pi−1k+1016Pik+316Pi+1k,Q2i+1k+1=Q2i+1,4k+1=132Pi−1k+1532Pik+1532Pi+1k+132Pi+2k.
In this figure, black polygon is the initial polygon made by the above scheme.Step 4.
Now, we calculate the displacement vectors from the points defined in (14) to the points defined in (13). These vectors are D2ik+1=D2i,4k+1=R2ik+1−Q2ik+1=−3/16Pi−1k+3/8Pik−3/16Pi+1k and D2i+1k+1=D2i+1,4k+1=R2i+1k+1−Q2i+1k+1=−3/32Pi−1k+3/32Pik+3/32Pi+1k−3/32Pi+2k. In Figure 4, the above displacement vectors and the other related vectors are shown by green vectors.Step 5.
In this step, we calculate vectorsαD2ik+1 and αD2i+1k+1, where α is any real number that can change the magnitude or the direction or both of the vectors D2ik+1 and D2i+1k+1. In Figure 4, these vectors are denoted by magenta lines.Step 6.
The last step of our method is to translate the points obtained by the refinement rules in (13) to the new position by using displacement vectors αD2ik+1 and αD2i+1k+1. So, we get following refinement rules of the new combined 4-point relaxed scheme(15)P2ik+1=P2i,4k+1=−316αPi−1k+1+38αPik−316αPi+1k,P2i+1k+1=P2i+1,4k+1=−116+332αPi−1k+916+332αPik+916+332αPi+1k−116+332αPi+2k.
In Figure4, the points of the above proposed scheme are denoted by black solid circles.Remark 2.
For the positive values of tension parameterα, the curves generated by the proposed subdivision schemes lie outside the initial polygon, whereas for negative values of α, the curves lie inside the initial polygon. For α=0, the curve generated by the proposed schemes passes through the initial control points.


## 3.1. Motivation and Contribution

In this article, we define a novel technique for constructing combined subdivision schemes by using interpolatory and approximating subdivision schemes with optimal performance in curves and surface fitting. Since the family of interpolatory schemes by Deslauriers and Dubuc [8] gives optimal performance in reproducing polynomials and the family of approximating B-spline schemes gives good performance in fitting curves with higher continuity, so we are motivated to unify them into a single family of schemes.The2n+2-point interpolatory subdivision schemes defined by Deslauriers and Dubuc [8] can reproduce polynomials up to degree 2n+1 and generate the limiting curves with C1. Whereas, the 2n+2-point relaxed B-spline approximating schemes are C4n-continuous, while the degree of polynomial reproduction of these schemes is only one. Since the discussed two schemes are the primal schemes, hence each of them is the combination of one vertex and one edge rules. The vertex rule of interpolatory schemes keeps the initial vertices at every level of subdivision, while the vertex rule of the approximating schemes updates the initial vertices at each level of subdivision. Similarly, the edge rule of each scheme subdivides every edge of the given polygon into two edges at each level of subdivision. The limit curves generated by the interpolatory and approximating schemes after 4 subdivision levels are shown in Figure 1. In this article, we construct a family of combined subdivision schemes with one parameter which controls the shape of the limit curve.Figure 1
Red bullets and red lines represent initial points and initial polygon, respectively. Blue bullets and blue curve are the points and limiting curve generated by the 4-point scheme by Deslauriers and Dubuc [8], respectively, after 4 subdivision levels. Whereas black bullets and black curve are the points and limiting curve generated by the 4-point relaxed B-spline scheme, respectively, after 4 subdivision levels.We construct the new family of schemes by the family of interpolatory schemes defined by Deslauriers and Dubuc [8] and the family of approximating B-spline schemes. Therefore, the proposed family of schemes carry the properties of these two types of schemes and give optimal numerical and mathematical results. From Figure 2. Figure 3, we can see the better performance of the proposed schemes than that of their parent schemes (schemes which are used in their construction). Figure 2 shows that if we choose the value of tension parameter for the proposed 4-point scheme between −2.5 and −2, then this scheme is good for fitting noisy data. Figure 3(c) shows that the curves fitted by the proposed 6-point scheme do not give the artifacts as presented by the 6-point scheme [8] in Figure 3(a). This figure also shows that the curve fitted by the proposed scheme preserve the shape of the initial polygon if we take value of tension parameter between −0.5 and 0, while the curve fitted by the 6-point B-spline scheme does not have this ability, as shown in Figure 3(b).Figure 2
Black bullets are the initial points, whereas the solid lines show the limit curves generated by the binary primal schemes. (a) 4-point interpolatory scheme, (b) 4-point B-spline scheme,and (c) proposed 4-point scheme forα=−2.5.
(a)(b)(c)Figure 3
Dotted lines and black bullets are the initial polygons and initial points, respectively. Whereas the solid lines show the limit curves generated by the binary primal schemes. (a) 6-point interpolatory scheme, (b) 6-point B-spline scheme, and (c) proposed 6-point scheme forα=−0.32.
(a)(b)(c)Construction of the family of schemes is discussed in coming subsections in detail.


## 3.2. Framework for the Construction of Family of Subdivision Schemes

The family of2n+2-point interpolatory subdivision schemes, constructed by Lagrange’s interpolatory polynomials presented by Deslauriers and Dubuc [8], is defined by two subdivision rules. The vertex rule is R2i,2n+2k+1=Pi,2n+2k, and the edge rule is(5)R2i+1,2n+2k+1=124n+1∑j=−n−1n−1jn+12j+12n+1n2n+1n+j+1Pi+j+1,2n+2k.The refinement rules of the family of2n+2-point relaxed approximating schemes, i.e. degree-4n+1 binary B-spline subdivision schemes, are(6)Q2i,2n+2k+1=124n+1∑j=02n4n+22j+1Pi+j−n,2n+2k,Q2i+1,2n+2k+1=124n+1∑j=02n+14n+22jPi+j−n,2n+2k,where n∈ℤ+. Let us denote the displacement vectors from the degree-4n+1 B-spline refinement points Q2i,2n+2k+1&Q2i+1,2n+2k+1 to the refinement points R2i,2n+2k+1&R2i+1,2n+2k+1 of 2n+2-point interpolatory subdivision scheme defined in (5) after one step of refinements by D2i,2n+2k+1&D2i+1,2n+2k+1, respectively. Hence, the displacement vectors are(7)D2i,2n+2k+1=R2i,2n+2k+1−Q2i,2n+2k+1,D2i+1,2n+2k+1=R2i+1,2n+2k+1−Q2i+1,2n+2k+1.Now, a new family of primal combined2n+2-point subdivision schemes can be obtained by translating the points R2i,2n+2k+1&R2i+1,2n+2k+1, that are provided by the binary interpolatory subdivision schemes (5) to the new position according to the displacement vectors αD2i,2n+2k+1&αD2i+1,2n+2k+1, respectively.(8)P2i,2n+2k+1=R2i,2n+2k+1+αD2i,2n+2k+1,P2i+1,2n+2k+1=R2i+1,2n+2k+1+αD2i+1,2n+2k+1,which can be further written as(9)P2i,2n+2k+1=−α24n+1∑j=0,j≠n2n4n+22j+1Pi+j−n,2n+2k+124n+124n+11+α−α×4n+22n+1Pi,2n+2k,P2i+1,2n+2k+1=124n+1∑j=02n+1−1j−n−1n+12j−2n−12n+1n2n+1j+α−1j−n−1n+12j−2n−1×2n+1n2n+1j−4n+22jPi+j−n,2n+2k.The rules defined in (9) are the refinement rules of the proposed family of 2n+2-point combined schemes, which are equivalent to the following general form:(10)P2i,2n+2k+1=∑j=02na2j+1,2n+2Pi+j−n,2n+2k,P2i+1,2n+2k+1=∑j=02n+1a2j,2n+2Pi+j−n,2n+2k.The mask symbol of the above scheme is(11)a2n+2z=∑j=04n+2aj,2n+2zj=1+z2n+222n+1A2n+2z,with(12)A2n+2z=∑j=02nAj,2n+2zj,where aj,2n+2:j=0,1,…,4n+2 and Aj,2n+2:j=0,1,…,2n are the coefficients of zj:j=0,1,…,4n+2 and zj:j=0,1,…,2n, respectively in (11) and (12).Remark 1.
Ifα⟶0, the family of proposed 2n+2-point schemes converges to the family of 2n+2-point interpolatory schemes proposed in [8]. Whereas if α⟶−1, the family of proposed 2n+2-point schemes converges to the family of 2n+2-point relaxed approximating B-spline schemes of degree-4n+1.


## 3.3. The Geometrical and Mathematical Interpretation of the Family of Schemes

The family of proposed schemes (9) is obtained by moving the points R2i,2n+2k+1 and R2i+1,2n+2k+1 of the family of schemes (5) to the new position according to the displacement vectors αD2i,2n+2k+1 and αD2i+1,2n+2k+1, respectively. In order to make the construction of the family of schemes understandable, we explain the following steps by fixing n=1 and k=0.Figure 4
Geometrical construction of the scheme fork=0 and n=1.Step 1.
We take the pointsPi−2,40=Pi−2k, Pi−1,40=Pi−1k, Pi,40=Pik, Pi+1,40=Pi+1k, Pi+2,40=Pi+2k, Pi+3,40=Pi+3k, Pi+4,40=Pi+4k, and Pi+5,40=Pi+5k as the initial control points, i.e. at zeroth level of subdivision. The points are shown by red bullets in Figure 4. In this figure, the combination of red lines makes the initial polygon.Step 2.
Now, we calculate pointsR2ik+1 and R2i+1k+1 which are denoted by blue solid squares in Figure 4. We calculate fifteen points (blue solid squares) by applying the following refinement rules of the 4-point interpolatory scheme of Deslauriers and Dubuc [8] on the initial points(13)R2ik+1=R2i,4k+1=Pik,R2i+1k+1=R2i+1,4k+1=−116Pi−1k+916Pik+916Pi+1k−116Pi+2k.
All the points inserted by the above subdivision scheme are shown in Figure4; however, we restrict our next calculations to only two points R2ik+1 and R2i+1k+1. In this figure, blue polygon is the initial polygon obtained from the scheme (13).Step 3.
In this step, we calculate and restrict next calculations to only the pointsQ2ik+1 and Q2i+1k+1 denoted by black solid squares. Again, the fifteen points, denoted by black solid squares in Figure 4, are calculated by the refinement rules of the 4-point relaxed binary B-spline scheme of degree-5 which is defined as follows:(14)Q2ik+1=Q2i,4k+1=316Pi−1k+1016Pik+316Pi+1k,Q2i+1k+1=Q2i+1,4k+1=132Pi−1k+1532Pik+1532Pi+1k+132Pi+2k.
In this figure, black polygon is the initial polygon made by the above scheme.Step 4.
Now, we calculate the displacement vectors from the points defined in (14) to the points defined in (13). These vectors are D2ik+1=D2i,4k+1=R2ik+1−Q2ik+1=−3/16Pi−1k+3/8Pik−3/16Pi+1k and D2i+1k+1=D2i+1,4k+1=R2i+1k+1−Q2i+1k+1=−3/32Pi−1k+3/32Pik+3/32Pi+1k−3/32Pi+2k. In Figure 4, the above displacement vectors and the other related vectors are shown by green vectors.Step 5.
In this step, we calculate vectorsαD2ik+1 and αD2i+1k+1, where α is any real number that can change the magnitude or the direction or both of the vectors D2ik+1 and D2i+1k+1. In Figure 4, these vectors are denoted by magenta lines.Step 6.
The last step of our method is to translate the points obtained by the refinement rules in (13) to the new position by using displacement vectors αD2ik+1 and αD2i+1k+1. So, we get following refinement rules of the new combined 4-point relaxed scheme(15)P2ik+1=P2i,4k+1=−316αPi−1k+1+38αPik−316αPi+1k,P2i+1k+1=P2i+1,4k+1=−116+332αPi−1k+916+332αPik+916+332αPi+1k−116+332αPi+2k.
In Figure4, the points of the above proposed scheme are denoted by black solid circles.Remark 2.
For the positive values of tension parameterα, the curves generated by the proposed subdivision schemes lie outside the initial polygon, whereas for negative values of α, the curves lie inside the initial polygon. For α=0, the curve generated by the proposed schemes passes through the initial control points.


## 4. Analysis of the Proposed Family of Subdivision Schemes

In this section, we prove the characteristics of the proposed subdivision schemes analytically. We prove few theorems and present various algorithms to check these properties.


### 4.1. Support

The support of a subdivision scheme represents the portion of the limit curve effected by the displacement of a single control point from its initial place. Now, we calculate the support of the proposed family of subdivision schemes.Theorem 1.
Ifϕ2n+2 is the basic limit function of the family of subdivision schemes (9), then, its support is suppϕ2n+2=−2n+1,2n+1.Proof.
To calculate support of the proposed family of subdivision schemes, we define a function which give zero value to all control points except one point,P00, whose value is one.(16)ϕi=Pi0=0fori=0,1fori≠0.
Letϕ2n+2:ℝ⟶ℝ be the basic limit function such that ϕ2n+2i/2k=Pi,2n+2k. Moreover, ϕi=ϕ2n+2i and Pi0=Pi,2n+20. Therefore, the support of basic limit function ϕ2n+2 is equal to the support of the subdivision scheme Sa2n+2.
When we apply a proposed2n+2-point relaxed scheme on the initial data Pi0, then at first subdivision step, the nonzero vertices are(17)ϕ2n+2−202n+121=P−202n+1,2n+21,P−202n+1+1,2n+21,…,P202n+1−1,2n+21,P202n+1,2n+21=ϕ2n+2202n+121.
At second subdivision step, the nonzero vertices are(18)ϕ2n+2−20+212n+122=P−20+212n+1,2n+22,P−20+212n+1+1,2n+22,…,P20+212n+1−1,2n+22,P20+212n+1,2n+22=ϕ2n+220+212n+122.
At third subdivision step, the nonzero vertices are(19)ϕ2n+2−20+21+222n+123=P−20+21+222n+1,2n+23,P−20+21+222n+1+1,2n+23,…,P20+21+222n+1−1,2n+23,P20+21+222n+1,2n+23=ϕ2n+220+21+222n+123.
Similarly, atk-th subdivision step, the nonzero vertices are(20)ϕ2n+2−∑j=0k−12j2n+12k=P−∑j=0k−12j2n+1,2n+2k,P−∑j=0k−12j2n+1+1,2n+2k,…,P∑j=0k−12j2n+1−1,2n+2k,P∑j=0k−12j2n+1,2n+2k=ϕ2n+2∑j=0k−12j2n+12k.
Hence, the support size of basic limit function is the difference between subscripts of the maximum nonzero vertex and the minimum nonzero vertex, i.e.(21)support size ofϕ2n+n2=∑j=0k−12j2n+12k−∑j=0k−12j2n+12k=22n+1∑j=0k−12j2k=22n+1∑j=0k12j.
Applying limitk⟶∞, we get support size of ϕ2n+2=22n+1. Hence, suppϕ2n+2=−2n+1,2n+1 is the support region of ϕ2n+2.


### 4.2. Smoothness Analysis

Now, we calculate the order of parametric continuity of the proposed subdivision schemes by using the Laurent polynomial method. Detailed information about refinement rules, Laurent polynomials, and convergence of a subdivision scheme can be found in [9–11]. The continuity of the subdivision schemes can be analyzed by the following theorems.Theorem 2 (see [10]).
A convergent subdivision schemeSa corresponding to the symbol(22)az=1+z2znbz,is Cn-continuous iff the subdivision scheme Sb corresponding to the symbol bz is convergent.Theorem 3.
The schemeSb corresponding to the symbol bz is convergent iff its difference scheme Sc corresponding to the symbol bz is contractive, where bz=1+zcz. The scheme Sc is contractive if(23)cl∞=max∑icj−2lil:0≤j<2l<1,l∈ℕ,where cil are the coefficients of the scheme Scl with symbol(24)clz=czcz2…cz2l−1.In the following theorem, we prove that the proposed subdivision schemes satisfy the condition which is necessary for the convergence of a subdivision schemes.Theorem 4.
The family of subdivision schemes with the refinement rules defined in (9) and (10) satisfies the basic sum rule.Proof.
The family of subdivision schemes (9) satisfies basic sum rule if(25)∑j=02na2j+1,2n+2=∑j=02n+1a2j,2n+2=1.
Since(26)∑j=02n4n+22j+1=∑j=02n+1−1j−n−1n+12j−2n−12n+1n2n+1j=∑j=02n+14n+22j=24n+1.
Hence,(27)∑j=02na2j+1,2n+2=−α24n+1∑j=02n4n+22j+1+1+α=−α24n+124n+1+1+α=1,and(28)∑j=02n+1a2j,2n+2=124n+1∑j=02n+1−1j−n−1n+12j−2n−12n+1n2n+1j1+α,−α24n+1∑j=02n+14n+22j=124n+124n+11+α−α24n+124n+1=1.
Therefore, the family of subdivision schemes with the refinement rules defined in (9) satisfy the basic sum rule which is also the necessary condition for the convergence of a subdivision scheme.
We use Theorems2 and 3 to design Algorithm 1. This algorithm is designed to calculate the level of parametric continuity of the limit curves generated by the proposed subdivision schemes. In Tables 1 and 2, we collect the results obtained from Algorithm 1 for L=1 and L=2, respectively. We use the step count method to find out the time complexity of the iterative Algorithm 1. Firstly, we compute the if-case time complexity.
Time complexity of Steps 2–15 of Algorithm 1 (if-case). Tables3–6.
Hence, the if-case time complexity of Algorithm 1 is(29)TIn,L=C1+C2+2C3+2C4+2C7+C8+2C9+2C10+C13+C14+2L+1C5+2L+1C6+4nC3+4nC4+4nC7+4nC9+4nC10+4n2LC5+4n2LC6,C˜1+2L+1C˜2+4nC˜3+4n2LC˜4∈O2Ln,where C˜1=C1+C2+2C3+2C4+2C7+C8+2C9+2C10+C13+C14, C˜2=C5+C6, C˜3=C3+C4+C7+C9+C10, and C˜4=C5+C6. Now, we compute the else-case time complexity of Algorithm 1.
Time complexity of Steps 16–25 of Algorithm 1 (else-case).
The else-case time complexity of Algorithm 1 is(30)TEn,L=C15+C16+2C17+2C18+C21+2C22+2C23+C24+2nC17+2nC18+2nC22+2nC23+2L+1C19+2L+1C20+2n2LC19+2n2LC20,C˜5+2L+1C˜6+2nC˜7+2n2LC˜8∈O2Ln,where C˜5=C15+C16+C17+C18+C21+2C22+2C23+C24, C˜6=C17+C18+C22+C23, C˜7=C19+C20, and C˜8=C19+C20. Hence, the time complexity of Algorithm 1 is O2Ln.Algorithm 1: Continuity of the schemes by Laurent polynomial.
(1)
input: The symbol of the proposed schemes, i.e. a2n+2z=a0,2n+2z0+a1,2n+2z1+a2,2n+2z2+a3,2n+2z3+⋯+a4n+2,2n+2z4n+2, n∈ℤ+, L∈ℤ+, α=−1 (optional) (⊳) ai,2n+2:i=0,1,…,4n+2 are the coefficients (depends on α) of zi:i=0,1,…,4n+2 respectively in a2n+2z(2)
ifα=−1then(3)
a2n+2z=1+z4n+2/24n+1(4)
forj=0 to 4n+1do(5)
calculate:c2n+2z=2j/1+zj+1a2n+2z(6)
forl=0 to 2L−1do(7)
calculate:Ml=∑mc2Lm+l,2n+2, m∈ℤ(8)
end for(9)
calculate:M= max Ml:l=0,1,…,2L−1(10)
ifM<1then(11)
return scheme corresponding to a2n+2z is Cj-continuous for α=−1(12)
else(13)
go to 26(14)
end if(15)
end for(16)
else(17)
a2n+2z=1+z2n+2/22n+1A0,2n+2z0+A1,2n+2z1+A2,2n+2z2+A3,2n+2z3+⋯+A2n,2n+2z2n (⊳) Ai,2n+2:i=0,1,…,2n are the coefficients (depends on α) of zi:i=0,1,…,2n respectively in a2n+2z(18)
forj=0 to 2n+1do(19)
calculate:c2n+2z=2j/1+zj+1a2n+2z(20)
forl=0 to 2L−1do(21)
calculate: an interval, sayα1,lj,α2,lj, for α by solving ∑mc2Lm+l,2n+2<1m, m∈ℤ(22)
end for(23)
calculate: intersection, sayα1j,α2j, of the 2L intervals α1j,α2j:l=0,1,…,2L−1(24)
return scheme is Cj-continuous for α∈α1j,α2j(25)
end for(26)
end if(27)
output: Level of continuity of the proposed schemes for an interval of α or for α=−1Table 1
Implementation of Algorithm 1 forL=1&n=1,2,3: specific range/value of α for which the proposed schemes have certain level of continuity.
n⟶123Schemes⟶ level of continuity↓4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)C0-continuous−4<α<1.333333333−2.888888889<α<0.8210526316−2.550443906<α<0.5234765235C1-continuous−2.666666667α<0.0000000000−2.133333333<α<0.0000000000−2.031746032<α<0.0000000000C2-continuous−2.666666667<α<0.0000000000−2.133333333<α<0.0000000000−1.997973658<α<0.0000000000C3-continuous−1.333333333<α<−.6666666667−1.600000000<α<−0.5333333333−1.523809524<α<−0.5079365079C4-continuousα=−1−1.542857143<α<−0.6285714286−1.500952381<α<−0.5257142857C5-continuous−1.100000000<α<−0.7000000000−1.245421245<α<−0.7765567766C6-continuousα=−1−1.182266010<α<−0.8669950739C7-continuousα=−1−1.028571429<α<−0.9714285714C8-continuousα=−1α=−1C9-continuousα=−1C10-continuousα=−1C11-continuousα=−1C12-continuousα=−1Table 2
Implementation of Algorithm 1 forL=2&n=1,2,3: specific range/value of α for which the proposed schemes have certain level of continuity.
n⟶123Schemes⟶ level of continuity↓4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)C0-continuous−5.271476716<α<1.568233303−3.988172738<α<1.01039496−3.383263797<α<0.857832085C1-continuous−3.581520882<α<0.248187548−3.049774258<α<0.304546042−2.799119823<α<0.326701153C2-continuous−2.666666667<α<0.0000000000−2.624109757<α<0.261216305−2.733101772<α<0.172894526C3-continuous−1.745355992<α<−0.6666666667−1.920669152<α<−0.4485616181−1.998133604<α<−0.3186270319C4-continuousα=−1−1.549222613<α<−0.6138320373−1.690568592<α<−0.4286478882C5-continuous−1.226979197<α<−0.6765487168−1.357201949<α<−0.7502504449C6-continuousα=−1−1.197285679<α<−0.850088102C7-continuousα=−1−1.074359658<α<−0.9559157159C8-continuousα=−1α=−1C9-continuousα=−1C10-continuousα=−1C11-continuousα=−1C12-continuousα=−1Table 3
Time complexity of Steps 2–15 of Algorithm 1 (if-case).
StepsCostFrequencyTotal cost2C11C13C21C24C34n+2C34n+25C44n+2C44n+26C52L4n+2C52L4n+27C62L4n+2C62L4n+29C74n+2C74n+28C81C810C94n+2C94n+211C104n+2C104n+212C111C1113C121C1214C131C1315C141C14Table 4
Time complexity of Steps 16–25 of Algorithm 1 (else-case).
StepsCostFrequencyTotal cost16C151C1517C161C1618C172n+2C172n+219C182n+2C182n+220C192L2n+2C192L2n+221C202L2n+2C202L2n+222C211C2123C222n+2C222n+224C232n+2C232n+225C241C24Table 5
Time complexity of Steps 2–11 of Algorithm 2 (if-case).
StepsCostFrequencyTotal cost2C11C13C21C24C34n+2C34n+25C44n+2C44n+26C54n+2C54n+27C64n+2C64n+28C71C79C81C810C91C911C101C10Table 6
Time complexity of Steps 12–21 of Algorithm 2 (else-case).
StepsCostFrequencyTotal cost12C111C1113C121C1214C132n+2C132n+215C142n+2C142n+216C152n+2C152n+217C162n+2C162n+218C171C1719C181C1820C171C1921C181C20


### 4.3. Degrees of Polynomial Generation and Polynomial Reproduction

Generation and reproduction degrees are used to examine the behaviors of a subdivision scheme when the original data points lie on the curve of a polynomial. We suppose that the original data points are taken from a polynomial of degreed. If the control points of the limit curve lie on the curve of the polynomial having same degree (i.e. d), then we say that the subdivision scheme generates polynomials of degree d. If the control points of the limit curve lie on curve of the same polynomial, then we say that the subdivision scheme reproduces polynomials of degree d. Mathematically, let Πd denote the space of polynomials of degree d and g, h∈Πd, an approximation operator O generates polynomials of degree d if Og=h∀g,h∈Πd, whereas O reproduces polynomials of degree d if Og=g∀g∈Πd. Furthermore, the generation degree of a subdivision scheme is the maximum degree of polynomials that can theoretically be generated by the scheme, provided that the initial data is taken correctly. Evidently, it is not less than the reproduction degree. The readers may consult [9, 12] to find out more details about polynomial generation and polynomial reproduction of a subdivision scheme. We design Algorithm 2 and Algorithm 3, based on the results given in [12], to check the degrees of polynomial generation and polynomial reproduction of proposed schemes, respectively. Outputs obtained by implementing these algorithms are summarized in Tables 7 and 8, respectively.Table 7
Implementation of Algorithm 2 forn=1,2,3,4.
n⟶1234Schemes⟶4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)10-point scheme (relaxed)Generation degree∀α3579Generation degreeα=−1591317Table 8
Implementation of Algorithm 3 forn=1,2,3,4.
n⟶1234Schemes⟶4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)10-point scheme (relaxed)Reproduction degree∀α1111Reproduction degreeα=03579Algorithm 2: Generation degree of the schemes.
(1)
input: The symbol of the proposed schemes, i.e. a2n+2z=a0,2n+2z0+a1,2n+2z1+a2,2n+2z2+a3,2n+2z3+⋯+a4n+2,2n+2z4n+2, n∈ℤ+ (⊳) ai,2n+2:i=0,1,…,4n+2 are the coefficients (depends on α) of zi:i=0,1,…,4n+2 respectively in a2n+2z(2)
ifα=−1then(3)
a2n+2z=1+z4n+2/24n+1(4)
forj=0 to 4n+1do(5)
calculate: (⊳)ajz|z=−1 denotes the j-th derivative of az evaluated at z=−1(6)
ifA=0then(7)
return scheme generates polynomials up to degree j for α=−1(8)
else(9)
go to 22(10)
end if(11)
end for(12)
else(13)
a2n+2z=1+z2n+2/22n+1A0,2n+2z0+A1,2n+2z1+A2,2n+2z2+A3,2n+2z3+⋯+A2n,2n+2z2n (⊳) Ai,2n+2:i=0,1,…,2n are the coefficients (depends on α) of zi:i=0,1,…,2n respectively in a2n+2z(14)
forj=0 to 2n+1do(15)
calculate:A=ajz|z=−1(16)
ifA=0then(17)
return scheme generates polynomials up to degree j for all α(18)
else(19)
go to 22(20)
end if(21)
end for(22)
end if(23)
output: degree of generation of the schemes corresponding to a2n+2z for all α or for α=−1.Algorithm 3: Reproduction degree of the schemes.
(1)
input: The symbol of the proposed schemes, i.e.a2n+2z=a0,2n+2z0+a1,2n+2z1+a2,2n+2z2+a3,2n+2z3+⋯+a4n+2,2n+2z4n+2=1+z2n+2/22n+1A0,2n+2z0+A1,2n+2z1+A2,2n+2z2+A3,2n+2z3+⋯+A2n,2n+2z2n, n∈ℤ+ (⊳) ai,2n+2:i=0,1,…,4n+2 are the coefficients (depends on α) of zi:i=0,1,…,4n+2 respectively in a2n+2z(2)
calculate:τ=a′z/2(3)
forj=0 to 4n+3do(4)
calculate:Aj=|a2n+2j|z=1, Bj=∏p=0j−1τ−p and Cj=a2n+2jz|z=−1(5)
ifAj=Bjthen and Cj=0(6)
scheme reproduce polynomials of degreej∀α(7)
else(8)
calculate:Aj, Bj and Cj for α=0(9)
ifAj=Bj and Cj=0 for α=0then(10)
scheme reproduce polynomials of degreej for α=0(11)
else(12)
go to 15(13)
end if(14)
end if(15)
end for(16)
output: degree of reproduction of the schemes corresponding to a2n+2z for all α or for α=0Now, we find the time complexity of Algorithm 2. Firstly, we compute the if-case (Steps 2–11) time complexity and then we find the else-case time complexity (Steps 12–22). Hence, the worst-case time complexity will be the time complexity of Algorithm 2.Time complexity of Steps 2–11 of Algorithm 2 (if-case).To calculate the time complexity of Steps 2–11, we either consider the total cost of Steps 6–7 or of Steps 8–9. So, we consider the worst-case which is Steps 6–7. Hence, the if-case time complexity of Algorithm 2 is(31)TIn=C1+C2+2C3+2C4+2C5+2C6+C9+C10+4nC3+4nC4+4nC5+4nC6,=C˜1+4nC˜2∈On,where C˜1=C1+C2+2C3+2C4+2C5+2C6+C9+C10 and C˜2=C3+C4+C5+C6. Now, we compute the else-case time complexity (Steps 12–21).Time complexity of Steps 12–21 of Algorithm 2 (else-case).To calculate time complexity of Steps 12–21, we ignore total cost of Steps 18–19. Therefore, the else-case time complexity of Algorithm 2 is(32)TEn=C11+C12+2C13+2C14+2C15+2C16+C19+C20+2nC13+2nC14+2nC15+2nC16=C˜3+2nC˜4∈On,where C˜3=C11+C12+2C13+2C14+2C15+2C16+C17+C18+C19+C20 and C˜4=C13+C14+C15+C16. Hence, time complexity of Algorithm 2 is On. In the same manner, we can prove that the time complexity of Algorithm 3 is also On.


### 4.4. Gibbs Oscillations

According to [13], linear subdivision schemes exhibit overshoots or undershoots Gibbs oscillations near to the points of discontinuity of a discontinuous function. The schemes that show undershoots generate curves free from oscillations while the schemes with overshoots give unpleasant oscillations in the limit curves. Let 0⩽ξ⩽h, and a function p is said to be discontinuous at a point ξ, if(33)∀x⩽ξ,px=p−xwithp−∈C∞−∞,ξ,∀x⩾ξ,px=p+xwithp+∈C∞ξ,∞,with p−ξ>p+ξ.A scheme has the overshoots near to the pointξ of discontinuity if(34)∀x⩽ξ,p−x<SA∞p0x,∀x⩾ξ,p+x>SA∞p0x.A scheme has the undershoots near to the pointξ of discontinuity if(35)∀x⩽ξ,p−x>SA∞p0x,∀x⩾ξ,p+x<SA∞p0x.Algorithm 4 is designed to calculate the range of tension parameterα for which the proposed schemes exhibit undershoot Gibbs oscillations. The results obtained from this algorithm are summarized in Table 9. We calculate the time complexity of Algorithm 4 which depends on the input value k by using the step count method. The time complexity of this algorithm does not depend on the input value n. Hence, the time complexity of this algorithm is Ok.Table 9
Implementation of Algorithm 4 fork=0,1,2,3 and n=1,2,3.
n⟶123Schemes⟶ k↓4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)0α<0α<0α<01−5.444444444<α<0−4.013223140<α<0−3.523131552<α<02−9.494261050<α<0−6.840555349<α<0−5.821687339<α<03−5.618133906<α<0−5.583827202<α<0−7.639304050<α<0Algorithm 4: Undershoot Gibbs phenomenon of the proposed schemes.
(1)
input:n∈ℤ+, k, Pi0:i∈ℤ (⊳) Pi0 are taken from a discontinuous function, i.e. Pi0=10fori∈−∞,−1,−10fori∈0,+∞.(2)
form=0 to k do(3)
calculate:P2i,nm+1=−α/24n+1∑j=0,j≠n2n4n+22j+1Pi+j−n,2n+2m+1/24n+124n+11+α−α×4n+22n+1Pi,2n+2m,(4)
calculate:P2i+1,2n+2m+1=1/24n+1∑j=02n+1−1j−n−1n+1/2j−2n−12n+1n2n+1j+α×−1j−n−1n+1/2j−2n−12n+1n2n+1j−4n+22jPi+j−n,2n+2m.5end for(6)
calculate: intervals ofα for which P−1,2n+20>Sa2n+2k+1P−1,2n+20(7)
calculate: intervals ofα for which P0,2n+20<Sa2n+2k+1P0,2n+20(8)
calculate: intersection of intervals ofα from Steps 6–7(9)
output: range of α for which the given scheme exibits undershoot Gibbs phenomenon at specific level of subdivision k.


### 4.5. Shape Preserving Properties

Here, we discuss the shape preserving properties, monotonicity and convexity preservation, of the proposed family of subdivision schemes. We prove that the proposed subdivision schemes preserve monotonicity and convexity for a special interval of tension parameter. For this, firstly, we calculate an interval ofα for which the proposed subdivision schemes having the bell-shaped mask. Then, by using results given in [13], we prove that the proposed schemes preserve monotonicity and convexity for a special interval of α.A2N-degree polynomial ∑j=02Nbjxj is said to be a polynomial with bell-shaped coefficients if it satisfied the following conditions:(36)suppbj=0,2N,bj>0forj∈0,2N,bj=b2N−jforj∈0,2N,bj<bj+1forj∈0,N−1.The mask symbol of the proposed family of schemes is defined in (10) which is a polynomial of degree-4n+2 satisfying the following two conditions:(37)suppaj,2n+2=0,4n+2,aj,2n+2=a4n+2−j,2n+2forj∈0,4n+2.The other two conditions depend on value ofα which can be calculated by Algorithm 5. The outputs obtained from Algorithm 5 are given in Table 10.Table 10
Implementation of Algorithm 5 forn=1,2,3.
n⟶123Schemes⟶4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)α1,α2⟶−2.666666667,−0.6666666667−1.200000000,−0.5263157895−1.721008403,−0.9523809524β1,β2⟶−1.555555556,0.6666666667−1.247058824,−0.5882352941−1.149842822,−0.6060606061γ1,γ2⟶−1.555555556,−0.6666666667−1.200000000,−0.5882352941−1.149842822,−0.9523809524Algorithm 5:Bell-shaped mask of the proposed schemes.
(1)
input: The mask aj,2n+2:j=0,1,…,4n+2 of the family of proposed schemes whose mask symbol is defined in (11), n∈ℤ+(2)
set:Aj=aj,2n+2(3)
forj=0 to 4n+2do(4)
calculate: an interval, sayα1j,α2j, for α by solving Aj>0(5)
end for(6)
calculate: intersection, sayα1,α2, of 4n+3 intervals α1j,α2j:j=0,1,…,4n+2(7)
forj=0 to 2ndo(8)
calculate: an interval, sayβ1j,β2j, for α by solving Aj<Aj+1(9)
end for(10)
calculate: intersection, sayβ1,β2, of 2n+1 intervals β1j,β2j:j=0,1,…,2n(11)
calculate: intersection, sayγ1,γ2, of 2 intervals α1,α2 and β1,β2(12)
returnα1,α2, β1,β2, γ1,γ2(13)
output: the proposed 2n+2-point scheme has a bell-shaped mask for α∈γ1,γ2Theorem 5.
The proposed 4-point, 6-point, and 8-point subdivision schemes preserve monotonicity for−1.555555556<α<−0.6666666667, −1.200000000<α<−0.5882352941, and −1.149842822<α<−0.9523809524, respectively.Proof.
By Theorem4, we see that the proposed subdivision schemes satisfy the basic sum rule. Also from Algorithm 5, we get that the proposed 4-point, 6-point, and 8-point subdivision schemes have bell-shaped mask for −1.555555556<α<−0.6666666667, −1.200000000<α<−0.5882352941, and −1.149842822<α<−0.9523809524, respectively, so it is easy to prove the required result by using ([13], Theorem 3).Theorem 6.
The proposed 4-point, 6-point, and 8-point subdivision schemes preserve convexity for−1.555555556<α<−0.6666666667, −1.200000000<α<−0.5882352941, and −1.149842822<α<−0.9523809524, respectively.Proof.
By Theorem4, we see that the proposed subdivision schemes satisfy the basic sum rule. Also from Algorithm 5, we get that the proposed 4-point, 6-point, and 8-point subdivision schemes have bell-shaped mask for −1.555555556<α<−0.6666666667, −1.200000000<α<−0.5882352941, and −1.149842822<α<−0.9523809524, respectively. Furthermore from (11), we can also see that the mask symbols of the proposed subdivision schemes have the factor 1+z2. Hence, the required result is proved by ([13], Theorem 4).
The proposed Algorithm 5 needsOn time to give output.


## 4.1. Support

The support of a subdivision scheme represents the portion of the limit curve effected by the displacement of a single control point from its initial place. Now, we calculate the support of the proposed family of subdivision schemes.Theorem 1.
Ifϕ2n+2 is the basic limit function of the family of subdivision schemes (9), then, its support is suppϕ2n+2=−2n+1,2n+1.Proof.
To calculate support of the proposed family of subdivision schemes, we define a function which give zero value to all control points except one point,P00, whose value is one.(16)ϕi=Pi0=0fori=0,1fori≠0.
Letϕ2n+2:ℝ⟶ℝ be the basic limit function such that ϕ2n+2i/2k=Pi,2n+2k. Moreover, ϕi=ϕ2n+2i and Pi0=Pi,2n+20. Therefore, the support of basic limit function ϕ2n+2 is equal to the support of the subdivision scheme Sa2n+2.
When we apply a proposed2n+2-point relaxed scheme on the initial data Pi0, then at first subdivision step, the nonzero vertices are(17)ϕ2n+2−202n+121=P−202n+1,2n+21,P−202n+1+1,2n+21,…,P202n+1−1,2n+21,P202n+1,2n+21=ϕ2n+2202n+121.
At second subdivision step, the nonzero vertices are(18)ϕ2n+2−20+212n+122=P−20+212n+1,2n+22,P−20+212n+1+1,2n+22,…,P20+212n+1−1,2n+22,P20+212n+1,2n+22=ϕ2n+220+212n+122.
At third subdivision step, the nonzero vertices are(19)ϕ2n+2−20+21+222n+123=P−20+21+222n+1,2n+23,P−20+21+222n+1+1,2n+23,…,P20+21+222n+1−1,2n+23,P20+21+222n+1,2n+23=ϕ2n+220+21+222n+123.
Similarly, atk-th subdivision step, the nonzero vertices are(20)ϕ2n+2−∑j=0k−12j2n+12k=P−∑j=0k−12j2n+1,2n+2k,P−∑j=0k−12j2n+1+1,2n+2k,…,P∑j=0k−12j2n+1−1,2n+2k,P∑j=0k−12j2n+1,2n+2k=ϕ2n+2∑j=0k−12j2n+12k.
Hence, the support size of basic limit function is the difference between subscripts of the maximum nonzero vertex and the minimum nonzero vertex, i.e.(21)support size ofϕ2n+n2=∑j=0k−12j2n+12k−∑j=0k−12j2n+12k=22n+1∑j=0k−12j2k=22n+1∑j=0k12j.
Applying limitk⟶∞, we get support size of ϕ2n+2=22n+1. Hence, suppϕ2n+2=−2n+1,2n+1 is the support region of ϕ2n+2.


## 4.2. Smoothness Analysis

Now, we calculate the order of parametric continuity of the proposed subdivision schemes by using the Laurent polynomial method. Detailed information about refinement rules, Laurent polynomials, and convergence of a subdivision scheme can be found in [9–11]. The continuity of the subdivision schemes can be analyzed by the following theorems.Theorem 2 (see [10]).
A convergent subdivision schemeSa corresponding to the symbol(22)az=1+z2znbz,is Cn-continuous iff the subdivision scheme Sb corresponding to the symbol bz is convergent.Theorem 3.
The schemeSb corresponding to the symbol bz is convergent iff its difference scheme Sc corresponding to the symbol bz is contractive, where bz=1+zcz. The scheme Sc is contractive if(23)cl∞=max∑icj−2lil:0≤j<2l<1,l∈ℕ,where cil are the coefficients of the scheme Scl with symbol(24)clz=czcz2…cz2l−1.In the following theorem, we prove that the proposed subdivision schemes satisfy the condition which is necessary for the convergence of a subdivision schemes.Theorem 4.
The family of subdivision schemes with the refinement rules defined in (9) and (10) satisfies the basic sum rule.Proof.
The family of subdivision schemes (9) satisfies basic sum rule if(25)∑j=02na2j+1,2n+2=∑j=02n+1a2j,2n+2=1.
Since(26)∑j=02n4n+22j+1=∑j=02n+1−1j−n−1n+12j−2n−12n+1n2n+1j=∑j=02n+14n+22j=24n+1.
Hence,(27)∑j=02na2j+1,2n+2=−α24n+1∑j=02n4n+22j+1+1+α=−α24n+124n+1+1+α=1,and(28)∑j=02n+1a2j,2n+2=124n+1∑j=02n+1−1j−n−1n+12j−2n−12n+1n2n+1j1+α,−α24n+1∑j=02n+14n+22j=124n+124n+11+α−α24n+124n+1=1.
Therefore, the family of subdivision schemes with the refinement rules defined in (9) satisfy the basic sum rule which is also the necessary condition for the convergence of a subdivision scheme.
We use Theorems2 and 3 to design Algorithm 1. This algorithm is designed to calculate the level of parametric continuity of the limit curves generated by the proposed subdivision schemes. In Tables 1 and 2, we collect the results obtained from Algorithm 1 for L=1 and L=2, respectively. We use the step count method to find out the time complexity of the iterative Algorithm 1. Firstly, we compute the if-case time complexity.
Time complexity of Steps 2–15 of Algorithm 1 (if-case). Tables3–6.
Hence, the if-case time complexity of Algorithm 1 is(29)TIn,L=C1+C2+2C3+2C4+2C7+C8+2C9+2C10+C13+C14+2L+1C5+2L+1C6+4nC3+4nC4+4nC7+4nC9+4nC10+4n2LC5+4n2LC6,C˜1+2L+1C˜2+4nC˜3+4n2LC˜4∈O2Ln,where C˜1=C1+C2+2C3+2C4+2C7+C8+2C9+2C10+C13+C14, C˜2=C5+C6, C˜3=C3+C4+C7+C9+C10, and C˜4=C5+C6. Now, we compute the else-case time complexity of Algorithm 1.
Time complexity of Steps 16–25 of Algorithm 1 (else-case).
The else-case time complexity of Algorithm 1 is(30)TEn,L=C15+C16+2C17+2C18+C21+2C22+2C23+C24+2nC17+2nC18+2nC22+2nC23+2L+1C19+2L+1C20+2n2LC19+2n2LC20,C˜5+2L+1C˜6+2nC˜7+2n2LC˜8∈O2Ln,where C˜5=C15+C16+C17+C18+C21+2C22+2C23+C24, C˜6=C17+C18+C22+C23, C˜7=C19+C20, and C˜8=C19+C20. Hence, the time complexity of Algorithm 1 is O2Ln.Algorithm 1: Continuity of the schemes by Laurent polynomial.
(1)
input: The symbol of the proposed schemes, i.e. a2n+2z=a0,2n+2z0+a1,2n+2z1+a2,2n+2z2+a3,2n+2z3+⋯+a4n+2,2n+2z4n+2, n∈ℤ+, L∈ℤ+, α=−1 (optional) (⊳) ai,2n+2:i=0,1,…,4n+2 are the coefficients (depends on α) of zi:i=0,1,…,4n+2 respectively in a2n+2z(2)
ifα=−1then(3)
a2n+2z=1+z4n+2/24n+1(4)
forj=0 to 4n+1do(5)
calculate:c2n+2z=2j/1+zj+1a2n+2z(6)
forl=0 to 2L−1do(7)
calculate:Ml=∑mc2Lm+l,2n+2, m∈ℤ(8)
end for(9)
calculate:M= max Ml:l=0,1,…,2L−1(10)
ifM<1then(11)
return scheme corresponding to a2n+2z is Cj-continuous for α=−1(12)
else(13)
go to 26(14)
end if(15)
end for(16)
else(17)
a2n+2z=1+z2n+2/22n+1A0,2n+2z0+A1,2n+2z1+A2,2n+2z2+A3,2n+2z3+⋯+A2n,2n+2z2n (⊳) Ai,2n+2:i=0,1,…,2n are the coefficients (depends on α) of zi:i=0,1,…,2n respectively in a2n+2z(18)
forj=0 to 2n+1do(19)
calculate:c2n+2z=2j/1+zj+1a2n+2z(20)
forl=0 to 2L−1do(21)
calculate: an interval, sayα1,lj,α2,lj, for α by solving ∑mc2Lm+l,2n+2<1m, m∈ℤ(22)
end for(23)
calculate: intersection, sayα1j,α2j, of the 2L intervals α1j,α2j:l=0,1,…,2L−1(24)
return scheme is Cj-continuous for α∈α1j,α2j(25)
end for(26)
end if(27)
output: Level of continuity of the proposed schemes for an interval of α or for α=−1Table 1
Implementation of Algorithm 1 forL=1&n=1,2,3: specific range/value of α for which the proposed schemes have certain level of continuity.
n⟶123Schemes⟶ level of continuity↓4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)C0-continuous−4<α<1.333333333−2.888888889<α<0.8210526316−2.550443906<α<0.5234765235C1-continuous−2.666666667α<0.0000000000−2.133333333<α<0.0000000000−2.031746032<α<0.0000000000C2-continuous−2.666666667<α<0.0000000000−2.133333333<α<0.0000000000−1.997973658<α<0.0000000000C3-continuous−1.333333333<α<−.6666666667−1.600000000<α<−0.5333333333−1.523809524<α<−0.5079365079C4-continuousα=−1−1.542857143<α<−0.6285714286−1.500952381<α<−0.5257142857C5-continuous−1.100000000<α<−0.7000000000−1.245421245<α<−0.7765567766C6-continuousα=−1−1.182266010<α<−0.8669950739C7-continuousα=−1−1.028571429<α<−0.9714285714C8-continuousα=−1α=−1C9-continuousα=−1C10-continuousα=−1C11-continuousα=−1C12-continuousα=−1Table 2
Implementation of Algorithm 1 forL=2&n=1,2,3: specific range/value of α for which the proposed schemes have certain level of continuity.
n⟶123Schemes⟶ level of continuity↓4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)C0-continuous−5.271476716<α<1.568233303−3.988172738<α<1.01039496−3.383263797<α<0.857832085C1-continuous−3.581520882<α<0.248187548−3.049774258<α<0.304546042−2.799119823<α<0.326701153C2-continuous−2.666666667<α<0.0000000000−2.624109757<α<0.261216305−2.733101772<α<0.172894526C3-continuous−1.745355992<α<−0.6666666667−1.920669152<α<−0.4485616181−1.998133604<α<−0.3186270319C4-continuousα=−1−1.549222613<α<−0.6138320373−1.690568592<α<−0.4286478882C5-continuous−1.226979197<α<−0.6765487168−1.357201949<α<−0.7502504449C6-continuousα=−1−1.197285679<α<−0.850088102C7-continuousα=−1−1.074359658<α<−0.9559157159C8-continuousα=−1α=−1C9-continuousα=−1C10-continuousα=−1C11-continuousα=−1C12-continuousα=−1Table 3
Time complexity of Steps 2–15 of Algorithm 1 (if-case).
StepsCostFrequencyTotal cost2C11C13C21C24C34n+2C34n+25C44n+2C44n+26C52L4n+2C52L4n+27C62L4n+2C62L4n+29C74n+2C74n+28C81C810C94n+2C94n+211C104n+2C104n+212C111C1113C121C1214C131C1315C141C14Table 4
Time complexity of Steps 16–25 of Algorithm 1 (else-case).
StepsCostFrequencyTotal cost16C151C1517C161C1618C172n+2C172n+219C182n+2C182n+220C192L2n+2C192L2n+221C202L2n+2C202L2n+222C211C2123C222n+2C222n+224C232n+2C232n+225C241C24Table 5
Time complexity of Steps 2–11 of Algorithm 2 (if-case).
StepsCostFrequencyTotal cost2C11C13C21C24C34n+2C34n+25C44n+2C44n+26C54n+2C54n+27C64n+2C64n+28C71C79C81C810C91C911C101C10Table 6
Time complexity of Steps 12–21 of Algorithm 2 (else-case).
StepsCostFrequencyTotal cost12C111C1113C121C1214C132n+2C132n+215C142n+2C142n+216C152n+2C152n+217C162n+2C162n+218C171C1719C181C1820C171C1921C181C20


## 4.3. Degrees of Polynomial Generation and Polynomial Reproduction

Generation and reproduction degrees are used to examine the behaviors of a subdivision scheme when the original data points lie on the curve of a polynomial. We suppose that the original data points are taken from a polynomial of degreed. If the control points of the limit curve lie on the curve of the polynomial having same degree (i.e. d), then we say that the subdivision scheme generates polynomials of degree d. If the control points of the limit curve lie on curve of the same polynomial, then we say that the subdivision scheme reproduces polynomials of degree d. Mathematically, let Πd denote the space of polynomials of degree d and g, h∈Πd, an approximation operator O generates polynomials of degree d if Og=h∀g,h∈Πd, whereas O reproduces polynomials of degree d if Og=g∀g∈Πd. Furthermore, the generation degree of a subdivision scheme is the maximum degree of polynomials that can theoretically be generated by the scheme, provided that the initial data is taken correctly. Evidently, it is not less than the reproduction degree. The readers may consult [9, 12] to find out more details about polynomial generation and polynomial reproduction of a subdivision scheme. We design Algorithm 2 and Algorithm 3, based on the results given in [12], to check the degrees of polynomial generation and polynomial reproduction of proposed schemes, respectively. Outputs obtained by implementing these algorithms are summarized in Tables 7 and 8, respectively.Table 7
Implementation of Algorithm 2 forn=1,2,3,4.
n⟶1234Schemes⟶4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)10-point scheme (relaxed)Generation degree∀α3579Generation degreeα=−1591317Table 8
Implementation of Algorithm 3 forn=1,2,3,4.
n⟶1234Schemes⟶4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)10-point scheme (relaxed)Reproduction degree∀α1111Reproduction degreeα=03579Algorithm 2: Generation degree of the schemes.
(1)
input: The symbol of the proposed schemes, i.e. a2n+2z=a0,2n+2z0+a1,2n+2z1+a2,2n+2z2+a3,2n+2z3+⋯+a4n+2,2n+2z4n+2, n∈ℤ+ (⊳) ai,2n+2:i=0,1,…,4n+2 are the coefficients (depends on α) of zi:i=0,1,…,4n+2 respectively in a2n+2z(2)
ifα=−1then(3)
a2n+2z=1+z4n+2/24n+1(4)
forj=0 to 4n+1do(5)
calculate: (⊳)ajz|z=−1 denotes the j-th derivative of az evaluated at z=−1(6)
ifA=0then(7)
return scheme generates polynomials up to degree j for α=−1(8)
else(9)
go to 22(10)
end if(11)
end for(12)
else(13)
a2n+2z=1+z2n+2/22n+1A0,2n+2z0+A1,2n+2z1+A2,2n+2z2+A3,2n+2z3+⋯+A2n,2n+2z2n (⊳) Ai,2n+2:i=0,1,…,2n are the coefficients (depends on α) of zi:i=0,1,…,2n respectively in a2n+2z(14)
forj=0 to 2n+1do(15)
calculate:A=ajz|z=−1(16)
ifA=0then(17)
return scheme generates polynomials up to degree j for all α(18)
else(19)
go to 22(20)
end if(21)
end for(22)
end if(23)
output: degree of generation of the schemes corresponding to a2n+2z for all α or for α=−1.Algorithm 3: Reproduction degree of the schemes.
(1)
input: The symbol of the proposed schemes, i.e.a2n+2z=a0,2n+2z0+a1,2n+2z1+a2,2n+2z2+a3,2n+2z3+⋯+a4n+2,2n+2z4n+2=1+z2n+2/22n+1A0,2n+2z0+A1,2n+2z1+A2,2n+2z2+A3,2n+2z3+⋯+A2n,2n+2z2n, n∈ℤ+ (⊳) ai,2n+2:i=0,1,…,4n+2 are the coefficients (depends on α) of zi:i=0,1,…,4n+2 respectively in a2n+2z(2)
calculate:τ=a′z/2(3)
forj=0 to 4n+3do(4)
calculate:Aj=|a2n+2j|z=1, Bj=∏p=0j−1τ−p and Cj=a2n+2jz|z=−1(5)
ifAj=Bjthen and Cj=0(6)
scheme reproduce polynomials of degreej∀α(7)
else(8)
calculate:Aj, Bj and Cj for α=0(9)
ifAj=Bj and Cj=0 for α=0then(10)
scheme reproduce polynomials of degreej for α=0(11)
else(12)
go to 15(13)
end if(14)
end if(15)
end for(16)
output: degree of reproduction of the schemes corresponding to a2n+2z for all α or for α=0Now, we find the time complexity of Algorithm 2. Firstly, we compute the if-case (Steps 2–11) time complexity and then we find the else-case time complexity (Steps 12–22). Hence, the worst-case time complexity will be the time complexity of Algorithm 2.Time complexity of Steps 2–11 of Algorithm 2 (if-case).To calculate the time complexity of Steps 2–11, we either consider the total cost of Steps 6–7 or of Steps 8–9. So, we consider the worst-case which is Steps 6–7. Hence, the if-case time complexity of Algorithm 2 is(31)TIn=C1+C2+2C3+2C4+2C5+2C6+C9+C10+4nC3+4nC4+4nC5+4nC6,=C˜1+4nC˜2∈On,where C˜1=C1+C2+2C3+2C4+2C5+2C6+C9+C10 and C˜2=C3+C4+C5+C6. Now, we compute the else-case time complexity (Steps 12–21).Time complexity of Steps 12–21 of Algorithm 2 (else-case).To calculate time complexity of Steps 12–21, we ignore total cost of Steps 18–19. Therefore, the else-case time complexity of Algorithm 2 is(32)TEn=C11+C12+2C13+2C14+2C15+2C16+C19+C20+2nC13+2nC14+2nC15+2nC16=C˜3+2nC˜4∈On,where C˜3=C11+C12+2C13+2C14+2C15+2C16+C17+C18+C19+C20 and C˜4=C13+C14+C15+C16. Hence, time complexity of Algorithm 2 is On. In the same manner, we can prove that the time complexity of Algorithm 3 is also On.


## 4.4. Gibbs Oscillations

According to [13], linear subdivision schemes exhibit overshoots or undershoots Gibbs oscillations near to the points of discontinuity of a discontinuous function. The schemes that show undershoots generate curves free from oscillations while the schemes with overshoots give unpleasant oscillations in the limit curves. Let 0⩽ξ⩽h, and a function p is said to be discontinuous at a point ξ, if(33)∀x⩽ξ,px=p−xwithp−∈C∞−∞,ξ,∀x⩾ξ,px=p+xwithp+∈C∞ξ,∞,with p−ξ>p+ξ.A scheme has the overshoots near to the pointξ of discontinuity if(34)∀x⩽ξ,p−x<SA∞p0x,∀x⩾ξ,p+x>SA∞p0x.A scheme has the undershoots near to the pointξ of discontinuity if(35)∀x⩽ξ,p−x>SA∞p0x,∀x⩾ξ,p+x<SA∞p0x.Algorithm 4 is designed to calculate the range of tension parameterα for which the proposed schemes exhibit undershoot Gibbs oscillations. The results obtained from this algorithm are summarized in Table 9. We calculate the time complexity of Algorithm 4 which depends on the input value k by using the step count method. The time complexity of this algorithm does not depend on the input value n. Hence, the time complexity of this algorithm is Ok.Table 9
Implementation of Algorithm 4 fork=0,1,2,3 and n=1,2,3.
n⟶123Schemes⟶ k↓4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)0α<0α<0α<01−5.444444444<α<0−4.013223140<α<0−3.523131552<α<02−9.494261050<α<0−6.840555349<α<0−5.821687339<α<03−5.618133906<α<0−5.583827202<α<0−7.639304050<α<0Algorithm 4: Undershoot Gibbs phenomenon of the proposed schemes.
(1)
input:n∈ℤ+, k, Pi0:i∈ℤ (⊳) Pi0 are taken from a discontinuous function, i.e. Pi0=10fori∈−∞,−1,−10fori∈0,+∞.(2)
form=0 to k do(3)
calculate:P2i,nm+1=−α/24n+1∑j=0,j≠n2n4n+22j+1Pi+j−n,2n+2m+1/24n+124n+11+α−α×4n+22n+1Pi,2n+2m,(4)
calculate:P2i+1,2n+2m+1=1/24n+1∑j=02n+1−1j−n−1n+1/2j−2n−12n+1n2n+1j+α×−1j−n−1n+1/2j−2n−12n+1n2n+1j−4n+22jPi+j−n,2n+2m.5end for(6)
calculate: intervals ofα for which P−1,2n+20>Sa2n+2k+1P−1,2n+20(7)
calculate: intervals ofα for which P0,2n+20<Sa2n+2k+1P0,2n+20(8)
calculate: intersection of intervals ofα from Steps 6–7(9)
output: range of α for which the given scheme exibits undershoot Gibbs phenomenon at specific level of subdivision k.


## 4.5. Shape Preserving Properties

Here, we discuss the shape preserving properties, monotonicity and convexity preservation, of the proposed family of subdivision schemes. We prove that the proposed subdivision schemes preserve monotonicity and convexity for a special interval of tension parameter. For this, firstly, we calculate an interval ofα for which the proposed subdivision schemes having the bell-shaped mask. Then, by using results given in [13], we prove that the proposed schemes preserve monotonicity and convexity for a special interval of α.A2N-degree polynomial ∑j=02Nbjxj is said to be a polynomial with bell-shaped coefficients if it satisfied the following conditions:(36)suppbj=0,2N,bj>0forj∈0,2N,bj=b2N−jforj∈0,2N,bj<bj+1forj∈0,N−1.The mask symbol of the proposed family of schemes is defined in (10) which is a polynomial of degree-4n+2 satisfying the following two conditions:(37)suppaj,2n+2=0,4n+2,aj,2n+2=a4n+2−j,2n+2forj∈0,4n+2.The other two conditions depend on value ofα which can be calculated by Algorithm 5. The outputs obtained from Algorithm 5 are given in Table 10.Table 10
Implementation of Algorithm 5 forn=1,2,3.
n⟶123Schemes⟶4-point scheme (relaxed)6-point scheme (relaxed)8-point scheme (relaxed)α1,α2⟶−2.666666667,−0.6666666667−1.200000000,−0.5263157895−1.721008403,−0.9523809524β1,β2⟶−1.555555556,0.6666666667−1.247058824,−0.5882352941−1.149842822,−0.6060606061γ1,γ2⟶−1.555555556,−0.6666666667−1.200000000,−0.5882352941−1.149842822,−0.9523809524Algorithm 5:Bell-shaped mask of the proposed schemes.
(1)
input: The mask aj,2n+2:j=0,1,…,4n+2 of the family of proposed schemes whose mask symbol is defined in (11), n∈ℤ+(2)
set:Aj=aj,2n+2(3)
forj=0 to 4n+2do(4)
calculate: an interval, sayα1j,α2j, for α by solving Aj>0(5)
end for(6)
calculate: intersection, sayα1,α2, of 4n+3 intervals α1j,α2j:j=0,1,…,4n+2(7)
forj=0 to 2ndo(8)
calculate: an interval, sayβ1j,β2j, for α by solving Aj<Aj+1(9)
end for(10)
calculate: intersection, sayβ1,β2, of 2n+1 intervals β1j,β2j:j=0,1,…,2n(11)
calculate: intersection, sayγ1,γ2, of 2 intervals α1,α2 and β1,β2(12)
returnα1,α2, β1,β2, γ1,γ2(13)
output: the proposed 2n+2-point scheme has a bell-shaped mask for α∈γ1,γ2Theorem 5.
The proposed 4-point, 6-point, and 8-point subdivision schemes preserve monotonicity for−1.555555556<α<−0.6666666667, −1.200000000<α<−0.5882352941, and −1.149842822<α<−0.9523809524, respectively.Proof.
By Theorem4, we see that the proposed subdivision schemes satisfy the basic sum rule. Also from Algorithm 5, we get that the proposed 4-point, 6-point, and 8-point subdivision schemes have bell-shaped mask for −1.555555556<α<−0.6666666667, −1.200000000<α<−0.5882352941, and −1.149842822<α<−0.9523809524, respectively, so it is easy to prove the required result by using ([13], Theorem 3).Theorem 6.
The proposed 4-point, 6-point, and 8-point subdivision schemes preserve convexity for−1.555555556<α<−0.6666666667, −1.200000000<α<−0.5882352941, and −1.149842822<α<−0.9523809524, respectively.Proof.
By Theorem4, we see that the proposed subdivision schemes satisfy the basic sum rule. Also from Algorithm 5, we get that the proposed 4-point, 6-point, and 8-point subdivision schemes have bell-shaped mask for −1.555555556<α<−0.6666666667, −1.200000000<α<−0.5882352941, and −1.149842822<α<−0.9523809524, respectively. Furthermore from (11), we can also see that the mask symbols of the proposed subdivision schemes have the factor 1+z2. Hence, the required result is proved by ([13], Theorem 4).
The proposed Algorithm 5 needsOn time to give output.


## 5. Numerical Examples

In this section, we show the numerical performance of the proposed schemes, based on the results which have proved in previous section. Figure5 displays the support of the subdivision scheme when the initial data is taken from a basic limit function defined in (16). Figure 6 shows the curves fitted by the proposed 2n+2-point subdivision schemes. It is clear from this figure that the tension parameter involved in the proposed subdivision schemes provides relaxation in drawing and designing different types of curves by using the same initial points. Figures 7 and 8 show the performance of the proposed subdivision schemes when the initial data is taken from monotonic and convex functions, respectively. Figures 9 and 10 show that the proposed subdivision schemes also carry the characteristics of keeping the shape of the initial polygon and of fitting the noisy data points, respectively, which is an important characteristic of the proposed family. In Literature, it is hard to find a single subdivision scheme which carries both characteristics simultaneously. The performance of the tensor product scheme of the proposed 4-point scheme in surface fitting is shown in Figure 11. Subfigures Figures 11(e), 11(f), 11(g), 11(h), 11(m), 11(n), 11(o), and 11(p), respectively are the mirror images in ij-plane of Subfigures 11(a), 11(b), 11(c), 11(d), 11(i), 11(j), 11(k), and 11(l).Figure 5
Dashed lines are the initial polylines, while the solid lines show the limit curves generated by the proposed schemes at different values of parameterα. (a) 4-point scheme. (b) 6-point scheme. (c) 8-point scheme.
(a)(b)(c)Figure 6
Black bullets are the initial control points, dashed lines polygons are the initial polygons, while black solid curves show the limit curves generated by the proposed subdivision schemes after 6 subdivision levels in (a) by the 4-point scheme from outer to inner withα=0.2,0.125,0,−0.25,−0.5,−1,−1.5,−1.75, in (b) by the 6-point scheme from outer to inner with α=0.25,0.125,0,−0.35,−0.65,−1,−1.5,−2 and in (c) by the 8-point scheme from outer to inner with α=0.4,0.2,0,−0.25,−0.5,−1,−1.8,−2.7.
(a)(b)(c)Figure 7
Curves generated by the proposed schemes after four subdivision steps where the initial data is taken from the monotonic functionfx=lnx:x∈0,18. (a) 4-point scheme. (b) 6-point scheme. (c) 8-point scheme.
(a)(b)(c)Figure 8
Curves generated by the proposed schemes after four subdivision steps where the initial data is taken from the convex functionfx=x2+2. (a) 4-point scheme. (b) 6-point scheme. (c) 8-point scheme.
(a)(b)(c)Figure 9
Solid lines in (a), (b), and (c) show the limit curve generated by the 4-point, 6-point, and 8-point proposed schemes. (a)α=−0.28, (b) α=−0.25, and (c) α=−0.19.
(a)(b)(c)Figure 10
Solid lines in (a), (b), and (c) show the limit curve generated by the 4-point, 6-point, and 8-point proposed schemes. (a)α=−2.5, (b) α=−2, and (c) α=−1.7.
(a)(b)(c)Figure 11
Surfaces produced by the tensor product of proposed 4-point relaxed scheme after four subdivision levels. (a) Initial mesh, (b)α=−2.5, (c) α=−2, (d) α=−1.5, (e), (f), (g), (h), (i) α=−1, (j) α=−0.5, (k) α=0, (l) α=0.25, (m), (n), (o), (p).
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)


## 6. Concluding Remarks

In this article, we have derived the general refinement rules of the family of2n+2-point primal binary schemes. The proposed schemes are originated from the schemes by Deslauriers and Dubuc [8]. We have also presented certain efficient algorithms with linear time complexity to check the properties of the proposed schemes. The beauty of the proposed family of schemes is that they carry the characteristics of both of its parent schemes. The proposed schemes show optimal continuity and polynomial generation. Proposed schemes reproduce polynomials up to degree one, while for specific value of tension parameters, they can reproduce polynomials up to degree 2n+1. The proposed schemes eliminate Gibbs phenomenon for negative values of tension parameter. Moreover, for a specific range of tension parameter, the proposed schemes also preserve monotonicity and convexity. The proposed schemes provide flexibility in fitting curves and surfaces, that is, using the same data points, we can variate the 2D and 3D models in between or around the control polygon/mesh. Proposed schemes are a good choice for noisy data. In future, we will derive the nonuniform form of the proposed schemes.Since from the methods used in our work, some of the most representative computational intelligence algorithms can be used to solve the problems, such as Monarch Butterfly Optimization [14, 15], Earthworm Optimization Algorithm [16], Elephant Herding Optimization [17], Moth Search Algorithm [18], Slime Mould Algorithm [19], Hunger Games Search [20], Runge Kutta Optimizer Method [21], Colony Predation Algorithm [22], and Harris Hawks Optimization Method [23]. These algorithms/methods can be used in the future to solve these type of problems. [24, 25].



---

*Source: 3661307-2022-06-01.xml*