# The Mask of Odd Pointsn-Ary Interpolating Subdivision Scheme

Authors: Ghulam Mustafa; Jiansong Deng; Pakeeza Ashraf; Najma Abdul Rehman
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

We present an explicit formula for the mask of odd pointsn-ary, for any odd n⩾3, interpolating subdivision schemes. This formula provides the mask of lower and higher arity schemes. The 3-point and 5-point a-ary schemes introduced by Lian, 2008, and (2m+1)-point a-ary schemes introduced by, Lian, 2009, are special cases of our explicit formula. Moreover, other well-known existing odd point n-ary schemes including the schemes introduced by Zheng et al., 2009, can easily be generated by our formula. In addition, error bounds between subdivision curves and control polygons of schemes are computed. It has been noticed that error bounds decrease when the complexity of the scheme decreases and vice versa. Also, as we increase arity of the schemes the error bounds decrease. Furthermore, we present brief comparison of total absolute curvature of subdivision schemes having different arity with different complexity. Convexity preservation property of scheme is also presented.


---

## Body

## 1. Introduction

Subdivision is an algorithmic technique to generate smooth curves and surfaces as a sequence of successively refined control polygons. We can survey subdivision as a process of taking a coarse shape and refining it to produce another shape that is more visually nice looking and smooth. Subdivision schemes are performed such that we take initial control polygon and make some iterations on it to make another shape. The resulting shape is then fed back into the subdivision scheme again and again until we get a reasonable level of detail. Beauty of this iterative process lies in elegant mathematical formulation and simple implementation.A general form of univariaten-ary subdivision scheme S which maps a polygon fk={fik}i∈ℤ to a refined polygon fk+1={fik+1}i∈ℤ is defined by
(1.1)fni+sk+1=∑j∈ℤ‍anj+sfi-jk,s=0,1,2,…,n-1,
where the set a={ai∣i∈ℤ} of coefficients is called mask of the subdivision scheme and n=2,3,…, stands for binary, ternary, and so on.Higher arity schemes are taking more attention now a days because of their useful and valuable properties. Higher arity schemes give a variety of different behaviors than lower arity schemes. It is noticed that higher arity schemes have higher smoothness and approximation order while their support is smaller compared to lower arity schemes. It is also observed that lower arity schemes have higher computational cost than higher arity schemes. Similarly increasing the number of points (complexity of the scheme) has also valuable upshots on smoothness of subdivision scheme.There are many even-pointn-ary subdivision schemes [1–5] in the literature for any n⩾2. Mustafa and Rehman [6] generalized and unified existing even-point n-ary subdivision schemes for any n⩾2.There are also odd-pointn-ary interpolating subdivision schemes [3, 7–9] in the literature for any odd n⩾3. So it is natural to look for a general formula which not only generalize and unify existing odd-point n-ary subdivision schemes but also provide the mask of higher arity schemes in a simple and efficient way. In this paper, we introduce an explicit formula which generalizes and unifies all existing odd-point n-ary interpolating subdivision schemes.Subdivision scheme offers a well-defined and competent way to represent smooth curves but question arises: How well control polygon of subdivision scheme approximates the limiting curve? To answer this question error bounds of subdivision schemes are to be computed. In [10], Mustafa and Hashmi presented an algorithm to calculate error bounds of n-ary subdivision schemes. By making use of this algorithm we present a brief comparison of the error bounds of some of our schemes. The result shows that as we increase arity of subdivision scheme the error bound decreases.A very frequent criterion to assess the worth of a subdivision scheme is its shape preserving properties. Convexity preservation is one of such properties. It is considered to be a geometrical property of subdivision scheme. So keeping this in mind, we describe convexity preserving property of one of the schemes. Moreover, some other important properties of subdivision like total absolute curvature and measure of deviation from convexity are also analyzed. Curvature is a geometrical criteria which truly describe the shape of objects. A brief comparison of our proposed family of schemes with other existing schemes is given.  Some  geometrical examples to show visual performance of scheme are also given.The paper is organized as follows: in Section2, some preliminary concepts are given, which are useful in the next sections. In Section 3, mask of odd-point n-ary scheme and some important results are given. In Section 4, comparison, application, error bounds, and total curvature of proposed family of schemes are presented. In Section 5, convexity preserving conditions of 5-point ternary scheme are derived. In the end of the paper, Section 6 which illustrates results and findings of the paper.


## 2. Preliminary Results

Here, we present some preliminary identities which play an important role in the construction of explicit formula for the mask of odd-pointsn-ary interpolating schemes for any odd n⩾3.LetΠ2b be the space of all polynomials of degree ⩽2b, where b is a nonnegative integer. If {Lk(x)}k=-bb is fundamental Lagrange polynomial corresponding to the nodes {k}k=-bb is defined by
(2.1)Lk(x)=∏j=-b,j≠kb‍x-jk-j,k=-b,…,b,
for which
(2.2)Lk(j)=δk,j,k,j=-b,…,b,(2.3)∑k=-bb‍p(k)Lk(x)=p(x),p∈Π2b,
where δk,j is Kronecker delta, defined as follows:
(2.4)δk,j={1,k=j,0,k≠j.
Then one can easily derive the following identities for each j=-b,…,b,
(2.5)Lj(b+1)=∏i=-bb‍(b+1-i)(b+1-j)(b+j)!(b-j)!(-1)b+j,(2.6)Lj(-b-1)=∏i=-bb‍(-b-1-i)(-b-1-j)(b+j)!(b-j)!(-1)b+j,(2.7)Lj(s3)=∏i=-bb‍(s-3i)(s-3j)(32b)(b+j)!(b-j)!(-1)b+j,s=-1,1,(2.8)Lj(s5)=∏i=-bb‍(s-5i)(s-5j)(52b)(b+j)!(b-j)!(-1)b+j,s=-2,-1,1,2.


## 3. Mask of(2b+3)-Point n-Ary Interpolating Scheme

In this section, we first find the mask of(2b+3)-point ternary and quinary interpolating schemes then by induction, we formulate a general formula for the mask of (2b+3)-point n-ary interpolating symmetric subdivision scheme.Lemma 3.1.
An explicit formula for the maska={aj}j=-3b-43b+4 of (2b+3)-point ternary interpolating scheme is defined by
(3.1)a3j=δj,0,a3j+s=Lj(s3)-a3b+3+sLj(b+1)-a3b+3-sLj(-b-1),a3b+3+t=a-(3b+3+t),
where b⩾0, s={t}-{0}, t=-((3-1)/2),…,((3-1)/2), Lj(b+1), Lj(-b-1), and Lj(s/3) are defined by (2.5)–(2.7), respectively.Proof.
To find the mask of(2b+3)-point ternary interpolating scheme, we consider the problem of finding a mask a={aj}j=-3b-43b+4 reproducing polynomial p of degree ⩽2b that is
(3.2)∑k‍aj+3kp(k)=p(j3),j∈ℤ,p∈Π2b.
Now by evaluating polynomialp at j=0,1,-1 and then by using (2.2) and (2.3), we get
(3.3)∑k=-bb‍a3kLj(k)=δj,0,(3.4)∑k=-b-1b+1‍a1+3kLj(k)=Lj(13),(3.5)∑k=-b-1b+1‍a-1+3kLj(k)=Lj(-13),
where j=-b,…,b.
By splitting left hand sides of (3.4)-(3.5) and then by (2.2), we get
(3.6)∑k=-b-1b+1‍a1+3kLj(k)=∑k=-bb‍a1+3kLj(k)+a3b+4Lj(b+1)+a-(3b+2)Lj(-b-1)=a3j+1+a3b+4Lj(b+1)+a3b+2Lj(-b-1),∑k=-b-1b+1‍a-1+3kLj(k)=∑k=-bb‍a-1+3kLj(k)+a3b+2Lj(b+1)+a-(3b+4)Lj(-b-1)=a3j-1+a3b+2Lj(b+1)+a3b+4Lj(-b-1).
Now, by substituting right hand sides of above equations into (3.4)-(3.5) and by (3.3), we get the general formula for the mask a={aj}j=-3b-43b+4 of (2b+3)-point ternary interpolating subdivision scheme
(3.7)a3j=δj,0,a3j+1=Lj(13)-a3b+4Lj(b+1)-a3b+2Lj(-b-1),a3j-1=Lj(-13)-a3b+2Lj(b+1)-a3b+4Lj(-b-1),
where j=-b,…,b and aj=a-j (symmetric condition, for j=1,…,3b+4), Lj(b+1), Lj(-b-1), Lj(1/3),  Lj(-1/3) are defined by (2.5)–(2.7).
By reformulating the above symmetric condition and (3.7), we obtain (3.1). This completes the proof.Lemma 3.2.
An explicit formula for the maska={aj}j=-5b-75b+7 of (2b+3)-point quinary interpolating scheme is defined by
(3.8)a5j=δj,0,a5j+s=Lj(s5)-a5b+5+sLj(b+1)-a5b+5-sLj(-b-1),a5b+5+t=a-(5b+5+t),
where  b⩾0,  s={t}-{0}, t=-((5-1)/2),…,((5-1)/2), Lj(b+1), Lj(-b-1), and Lj(s/5) are defined by (2.5), (2.6) and (2.8), respectively.Proof.
Following the procedure of Lemma3.1, one can easily derive the following explicit formula for the mask a={aj}j=-5b-75b+7 of (2b+3)-point quinary interpolating subdivision scheme
(3.9)a5j=δj,0,a5j+1=Lj(15)-a5b+6Lj(b+1)-a5b+4Lj(-b-1),a5j-1=Lj(-15)-a5b+4Lj(b+1)-a5b+6Lj(-b-1),a5j+2=Lj(25)-a5b+7Lj(b+1)-a5b+3Lj(-b-1),a5j-2=Lj(-25)-a5b+3Lj(b+1)-a5b+7Lj(-b-1),
where j=-b,…,b and aj=a-j (symmetric condition, for j=1,…,5b+7), Lj(b+1), Lj(-b-1), Lj(1/5), Lj(-1/5), Lj(2/5), Lj(-2/5) are defined by (2.5), (2.6) and (2.8), respectively.
By reformulating the above symmetric condition and (3.9), we get (3.8). This completes the proofBy Lemmas3.1 and 3.2 with change of notations and by induction, we get the following theorem.Theorem 3.3.
Ifn stands for n-ary subdivision scheme for any odd n⩾3, b⩾0, j=-b,…,b,  t=-((n-1)/2),…,((n-1)/2) and s={t}-{0}, an explicit formula for the mask of (2b+3)-point n-ary interpolating scheme is defined by
(3.10)anj=δj,0,(3.11)anj+s=A(b,j,n,s)-anb+n+sB(b,j)-anb+n-sC(b,j),(3.12)anb+n+t=a-(nb+n+t),
where
(3.13)A(b,j,n,s)=∏i=-bb‍(s-ni)(s-nj)n2b(b+j)!(b-j)!(-1)b+j,B(b,j)=∏i=-bb‍(b+1-i)(b+1-j)(b+j)!(b-j)!(-1)b+j,C(b,j)=∏i=-bb‍(-b-1-i)(-b-1-j)(b+j)!(b-j)!(-1)b+j,
and the free parameter anb+n+t can be explicitly defined as
(3.14)anb+n+t=∏i=02b+1‍(bn-t-in)n2b+2(2b+2)!.Remark 3.4.
(i) It is to be noted that the scheme (3.10)–(3.12) has anb+n+t free parameters for (2b+3)-point n-ary interpolating scheme. By introducing free parameters we offer more flexibility for curve designing.
(ii) It is alsoclear that the scheme (3.10)–(3.14) has no free parameters for (2b+3)-point n-ary interpolating scheme.
(iii) We can see that the scheme generated by the mask (3.10)–(3.12) satisfies the polynomial reproducing property up to degree 2b, because this property is the starting point of the construction of the mask as formulated in (3.2).Remark 3.5.
Following are some lower and higher arity schemes generated by (3.10)–(3.14) with and without free parameters.
(i) If{n=13,b=0} then by (3.10)–(3.14), we get 3-point 13-ary interpolating scheme:
(3.15)1169{57,45,34,24,15,7,0,-6,-11,-15,-18,-20,-21,113,144,153,160,165,168,1,168,165,160,153,144,133,-21,-20,-18,-15,-11,-6,0,7,15,24,34,45,57}.
(ii) If{n=11,b=0} then by (3.10)–(3.14), we get 3-point undenary (i.e., 11-ary) interpolating scheme:
(3.16)1121{40,30,21,13,6,0,-5,-9,-12,-14,-15,96,105,112,117,120,121,120,117,112,105,96,-15,-14,-12,-9,-5,0,6,13,21,30,40}.
(iii)  If{n=9,b=0} then by (3.10)–(3.14), we get 3-point nonary (i.e., 9-ary) interpolating scheme:
(3.17)181{26,18,11,5,0,-4,-7,-9,-10,65,72,77,80,81,80,77,72,65,-10,-9,-7,-4,0,5,11,18,26}.
(iv) If{n=7,b=0} then by (3.10)–(3.14), we get 3-point septenary (i.e., 7-ary) interpolating scheme:
(3.18)149{15,9,4,0,-3,-5,-6,40,45,48,49,48,45,40,-6,-5,-3,0,4,9,15}.
(v) By setting{n=5,b=0} and then by (3.10)–(3.14), we get the following mask of new 3-point quinary (i.e., 5-ary) interpolating scheme:
(3.19)125{7,3,0,-2,-3,21,24,25,24,21,-3,-2,0,3,7}.
(vi) For{n=3,b=1,a5=w1,a6=0,a7=w2}, in (3.10)–(3.14), we get the following 5-point ternary (i.e., 3-ary) interpolating schemes with two parameters:
(3.20){w2,0,w1,29-w1-3w2,0,-19-3w1-w2,89+3w1+3w2,1,89+3w1+3w2,-19-3w1-w2,0,29-w1-3w2,w1,0,w2}.
(vii) For{n=3,b=0,a2=v1,a3=0,a4=v2}, in (3.10)–(3.12), we get the following 3-point ternary (i.e., 3-ary) interpolating schemes with two parameters
(3.21){v2,0,v1,1-v1-v2,1,1-v1-v2,v1,0,v2}.Remark 3.6.
Here, we see that existing schemes are either special cases of our scheme or can be generated by our explicit formula.(i)
By setting{n=3,b=0} in (3.10)–(3.14), we get mask of Lian ([9], Equation (22)) 3-point ternary interpolating scheme.(ii)
If{n=3,b=1} in (3.10)–(3.14), we get mask of Lian ([9], Equation (23)) 5-point ternary interpolating scheme.(iii)
We can easily build mask of 3-pointa-ary interpolating scheme ([9], Equations (12)–(14)), by setting {n=a,b=0} in (3.10)–(3.14).(iv)
Similarly, we can generate mask of 5-pointa-ary interpolating scheme ([9], Equations (15) – (17)), by taking {n=a,b=1} in (3.10)–(3.14).(v)
If{n=3,b=2} then by (3.10)–(3.14), we can build 7-point ternary scheme of ([3], Equations (42)–(44)).(vi)
The(2m+1)-point a-ary schemes ([3], Equations (11)-(12)) can easily be generated from our scheme listed in (3.10)–(3.14) by setting {n=a,b=m-1}.(vii)
By takingw1=4/81+u, and w2=u, in (3.20), we get mask of 5-point ternary interpolating scheme of Zheng et al. ([8], Equation (7)).(viii)
Ifv1=-1/3+u, and v2=u, in (3.21), we obtain mask of 3-point ternary interpolating scheme of Zheng et al. ([8], Equation (5)). Similarly one can easily derive the mask of (2n-1)-point ternary interpolating scheme of [8] from (3.10)–(3.12).(ix)
In casev2=v1+1/3, in (3.21), we get Hassan and Dodgson's 3-point ternary interpolating scheme [7].


## 4. Comparison, Applications, Error Bounds, and Total Absolute Curvature

In this section, first we present comparison of our proposed explicit formula with the existing explicit formula/algorithms for generating the masks of schemes. After that, we give visual performance among lower and higher arity schemes. Then we give a brief overview of error bounds of schemes. At the end, we give a comparison of total curvature of subdivision schemes for different arity with different complexity.


### 4.1. Comparison

Here is the comparison of our proposed explicit formula with the existing explicit formula/algorithms.(i)
All the well-known odd-pointsn-ary for any odd n⩾3 interpolating existing schemes are either special cases or can be easily generated by our proposed explicit formula while existing explicit formula/algorithms [3, 7–9] do not have this characteristic.(ii)
Lian’s explicit formulae [3, 9] generate the masks of only nonparametric schemes while our proposed explicit formula generate the masks of parametric as well as nonparametric schemes.(iii)
Zheng et al. [8] introduced an algorithm to generate only (2n-1)-point ternary interpolating subdivision schemes while we suggested explicit formula for any odd-points n-ary interpolating schemes for any odd n⩾3.(iv)
Hassan and Dodgson [7] 3-point ternary interpolating scheme is special case of our proposed explicit formula for mask of the schemes.


### 4.2. Applications

In Figure1, we give comparison among different arity schemes generated in this paper to show their performance. Refined polygons generated by different arity schemes after first subdivision level are shown and compared in this figure. This figure indicates that higher arity schemes converge to limit curve faster than lower arity schemes.Dotted lines indicate original control polygon while continuous curves are generated by 3-point interpolating 3-ary, 5-ary, 7-ary, 9-ary, 11-ary, and 13-ary schemes (3.15)–(3.19) and (3.21). Small squares indicate newly inserted points after first subdivision level.
(a)
3-point 3-ary, 1st subdivision level
(b)
3-point 5-ary, 1st subdivision level
(c)
3-point 7-ary, 1st subdivision level
(d)
3-point 9-ary, 1st subdivision level
(e)
3-point 11-ary, 1st subdivision level
(f)
3-point 13-ary, 1st subdivision level


### 4.3. Error Bounds

Subdivision is considered to be a very important tool in geometric modeling and shape designing. This approach is included in the control polygon paradigm. There arises an important question in the application of this type of procedure. How to estimate theerror(distance) between limit curve and its control polygon? To respond this question, here we present a collection of expressions, inequalities, and results described in [10].Given a control polygon composed of a sequence of control pointsfik∈ℝN, i∈ℤ, N⩾1. An n-ary subdivision curve (1.1) is re-defined by
(4.1)fni+αk+1=∑j=0m‍aα,jfi+jk,α=0,1,…,n-1,
where m>0 and
(4.2)∑j=0m‍aα,j=1,α=0,1,…,n-1.The set of coefficients{aα,j,α=0,1,…,n-1}j=0m is called subdivision mask. Given initial values  fi0∈ℝN, i∈ℤ. Then in the limit k→∞, the process (4.1) defines an infinite set of points in ℝN. The sequence of control points {fik} is related, in a natural way, with the diadic mesh points tik=i/nk, i∈ℤ. The process then defines a scheme whereby fnik+1 and fni+nk+1 replace the values fik and fi+1k at the mesh points tnik+1=tik and tni+nk+1=ti+1k, respectively, while fni+αk+1 is inserted at the new mesh points tni+αk+1=(1/n)((n-α)tik+αti+1k) for α=1,2,…,n-1.Given initial control polygonfi0=fi, i∈ℤ, let the values fik, k⩾1 be defined recursively by subdivision process  (4.1) together with (4.2). Suppose Fk is the piecewise linear interpolant to the values fik and F∞ is the limit curve of the process (4.1). If δ<1 then the error bound between limit curve and its control polygon after k-fold subdivision is
(4.3)∥Fk-F∞∥∞⩽γχ((δ)k1-δ),
where
(4.4)χ=maxi∥fi+10-fi0∥,δ=maxβ{|∑j=0m‍bβ,j|,β=0,1,…,n-1},
where
(4.5)bβ,j=∑t=0j‍(aβ,t-aβ+1,t),β=0,1,…,n-2,bn-1,j=a0,j-∑β=0n-2‍bβ,j,
also
(4.6)γ=maxα{|∑j=0m-1‍a~α,j|,α=0,1,…,n-1},
where
(4.7)a~α,0=∑t=1maα,t-αn,a~α,j=∑t=j+1maα,t,j⩾1.α=0,1,…,n-1,Rest of the section is devoted to the computation of error bounds between limit curve and their control polygon afterk-fold subdivision of (2b+3)-point n-ary interpolating scheme for different values of b≥0, k≥1, and  n≥3, by using (4.3) with χ=0.1.Error bounds of proposed odd-pointn-ary subdivision scheme at different subdivision levels are shown in Figure 2. From this figure, we have the following conclusions: Error bounds decrease with the increase of subdivision levels. Error bounds are directly proportional to the number of points involved (complexity of the scheme) to insert a point at next subdivision level. It is also observed that error bounds decrease with the increase of arity of the schemes.(a) Presents a comparison among error bounds of 3-pointn-ary interpolating scheme, i.e., for n=3,5,7,9. (b) Presents a comparison among error bounds of 5-point n-ary interpolating scheme, i.e., for n=3,5,7,9. (c) Presents a comparison among error bounds of 2b+3-point ternary interpolating scheme, i.e., for b=0,1,2,3. Here k presents subdivision level, E presents error bound and n presents arity of subdivision scheme.
(a)
(b)
(c)


### 4.4. Total Absolute Curvature

Here is the brief comparison of total absolute curvature (TAC) of interpolating subdivision schemes of different arity and complexity of the scheme. TAC of 3-point, 5-point, and 7-point interpolating scheme is computed by keeping arity 3. Also TAC is calculated for 3-point, 5-point, and 7-point interpolating scheme by keeping arity 5. Figure3 shows graphical representation of TAC of subdivision schemes. Same initial polygon is taken for all subdivision schemes to compute TAC. From Figure 3, it is clear that as we increase the arity TAC is also increased and as we increase the complexity of the scheme TAC is decreased. Figure 4 presents comparison of TAC among different values of parameter of 3-point ternary interpolating scheme (3.21), here we set v2=v1-1/3 and range of v2 is (0.2222,0.3333). From Figure 4, it is clear that as we increase value of parameter from left to right in the parametric interval (0.2222,0.3333), TAC of 3-point ternary interpolating scheme (3.21) is decreased.Comparison of total absolute curvature of 3-point ternary and 3-point quinary, 5-point ternary and 5-point quinary, and 7-point ternary and 7-point quinary interpolating schemes. HereL represents total absolute curvature and k represents number of iterations.
(a)
3-point ternary
(b)
3-point quinary
(c)
5-point ternary
(d)
5-point quinary
(e)
7-point ternary
(f)
7-point quinaryPresents comparison among total absolute curvature of 3-point ternary interpolating scheme for different values of parameter. HereL represents total absolute curvature and k represents number of iterations.
(a)
forv2=0.2333
(b)
forv2=0.2888
(c)
forv2=0.3111The total curvature and total absolute curvature are same for a closed convex polygonal curve and both are equal to2π. Hence for a nonconvex curve the measure of deviation (referred as D) from the convex curve can be calculated by subtracting TAC of nonconvex curve from TAC of convex curve that is 2π. In Table 1, we have calculated measure of deviation of convexity of 3-point and 5-point ternary interpolating scheme at different subdivision level. Figure 5 presents graphical representation of measure of deviation of 3-point and 5-point ternary interpolating scheme.Table 1
Measure of deviation of convexity of 3-point and 5-point ternary scheme. Herek presents the level of iteration and D is measure of deviation.
k
Scheme
D
Scheme
D
2
3-point
0.000000
5-point
0.000000
3
⋯
−0.716814
⋯
0.000000
4
⋯
−3.716814
⋯
−0.000001
5
⋯
−8.716814
⋯
−0.000011Presents measure of deviation of convexity of 3-point and 5-point ternary interpolating scheme.
(a)
3-point ternary
(b)
5-point ternary


## 4.1. Comparison

Here is the comparison of our proposed explicit formula with the existing explicit formula/algorithms.(i)
All the well-known odd-pointsn-ary for any odd n⩾3 interpolating existing schemes are either special cases or can be easily generated by our proposed explicit formula while existing explicit formula/algorithms [3, 7–9] do not have this characteristic.(ii)
Lian’s explicit formulae [3, 9] generate the masks of only nonparametric schemes while our proposed explicit formula generate the masks of parametric as well as nonparametric schemes.(iii)
Zheng et al. [8] introduced an algorithm to generate only (2n-1)-point ternary interpolating subdivision schemes while we suggested explicit formula for any odd-points n-ary interpolating schemes for any odd n⩾3.(iv)
Hassan and Dodgson [7] 3-point ternary interpolating scheme is special case of our proposed explicit formula for mask of the schemes.


## 4.2. Applications

In Figure1, we give comparison among different arity schemes generated in this paper to show their performance. Refined polygons generated by different arity schemes after first subdivision level are shown and compared in this figure. This figure indicates that higher arity schemes converge to limit curve faster than lower arity schemes.Dotted lines indicate original control polygon while continuous curves are generated by 3-point interpolating 3-ary, 5-ary, 7-ary, 9-ary, 11-ary, and 13-ary schemes (3.15)–(3.19) and (3.21). Small squares indicate newly inserted points after first subdivision level.
(a)
3-point 3-ary, 1st subdivision level
(b)
3-point 5-ary, 1st subdivision level
(c)
3-point 7-ary, 1st subdivision level
(d)
3-point 9-ary, 1st subdivision level
(e)
3-point 11-ary, 1st subdivision level
(f)
3-point 13-ary, 1st subdivision level


## 4.3. Error Bounds

Subdivision is considered to be a very important tool in geometric modeling and shape designing. This approach is included in the control polygon paradigm. There arises an important question in the application of this type of procedure. How to estimate theerror(distance) between limit curve and its control polygon? To respond this question, here we present a collection of expressions, inequalities, and results described in [10].Given a control polygon composed of a sequence of control pointsfik∈ℝN, i∈ℤ, N⩾1. An n-ary subdivision curve (1.1) is re-defined by
(4.1)fni+αk+1=∑j=0m‍aα,jfi+jk,α=0,1,…,n-1,
where m>0 and
(4.2)∑j=0m‍aα,j=1,α=0,1,…,n-1.The set of coefficients{aα,j,α=0,1,…,n-1}j=0m is called subdivision mask. Given initial values  fi0∈ℝN, i∈ℤ. Then in the limit k→∞, the process (4.1) defines an infinite set of points in ℝN. The sequence of control points {fik} is related, in a natural way, with the diadic mesh points tik=i/nk, i∈ℤ. The process then defines a scheme whereby fnik+1 and fni+nk+1 replace the values fik and fi+1k at the mesh points tnik+1=tik and tni+nk+1=ti+1k, respectively, while fni+αk+1 is inserted at the new mesh points tni+αk+1=(1/n)((n-α)tik+αti+1k) for α=1,2,…,n-1.Given initial control polygonfi0=fi, i∈ℤ, let the values fik, k⩾1 be defined recursively by subdivision process  (4.1) together with (4.2). Suppose Fk is the piecewise linear interpolant to the values fik and F∞ is the limit curve of the process (4.1). If δ<1 then the error bound between limit curve and its control polygon after k-fold subdivision is
(4.3)∥Fk-F∞∥∞⩽γχ((δ)k1-δ),
where
(4.4)χ=maxi∥fi+10-fi0∥,δ=maxβ{|∑j=0m‍bβ,j|,β=0,1,…,n-1},
where
(4.5)bβ,j=∑t=0j‍(aβ,t-aβ+1,t),β=0,1,…,n-2,bn-1,j=a0,j-∑β=0n-2‍bβ,j,
also
(4.6)γ=maxα{|∑j=0m-1‍a~α,j|,α=0,1,…,n-1},
where
(4.7)a~α,0=∑t=1maα,t-αn,a~α,j=∑t=j+1maα,t,j⩾1.α=0,1,…,n-1,Rest of the section is devoted to the computation of error bounds between limit curve and their control polygon afterk-fold subdivision of (2b+3)-point n-ary interpolating scheme for different values of b≥0, k≥1, and  n≥3, by using (4.3) with χ=0.1.Error bounds of proposed odd-pointn-ary subdivision scheme at different subdivision levels are shown in Figure 2. From this figure, we have the following conclusions: Error bounds decrease with the increase of subdivision levels. Error bounds are directly proportional to the number of points involved (complexity of the scheme) to insert a point at next subdivision level. It is also observed that error bounds decrease with the increase of arity of the schemes.(a) Presents a comparison among error bounds of 3-pointn-ary interpolating scheme, i.e., for n=3,5,7,9. (b) Presents a comparison among error bounds of 5-point n-ary interpolating scheme, i.e., for n=3,5,7,9. (c) Presents a comparison among error bounds of 2b+3-point ternary interpolating scheme, i.e., for b=0,1,2,3. Here k presents subdivision level, E presents error bound and n presents arity of subdivision scheme.
(a)
(b)
(c)


## 4.4. Total Absolute Curvature

Here is the brief comparison of total absolute curvature (TAC) of interpolating subdivision schemes of different arity and complexity of the scheme. TAC of 3-point, 5-point, and 7-point interpolating scheme is computed by keeping arity 3. Also TAC is calculated for 3-point, 5-point, and 7-point interpolating scheme by keeping arity 5. Figure3 shows graphical representation of TAC of subdivision schemes. Same initial polygon is taken for all subdivision schemes to compute TAC. From Figure 3, it is clear that as we increase the arity TAC is also increased and as we increase the complexity of the scheme TAC is decreased. Figure 4 presents comparison of TAC among different values of parameter of 3-point ternary interpolating scheme (3.21), here we set v2=v1-1/3 and range of v2 is (0.2222,0.3333). From Figure 4, it is clear that as we increase value of parameter from left to right in the parametric interval (0.2222,0.3333), TAC of 3-point ternary interpolating scheme (3.21) is decreased.Comparison of total absolute curvature of 3-point ternary and 3-point quinary, 5-point ternary and 5-point quinary, and 7-point ternary and 7-point quinary interpolating schemes. HereL represents total absolute curvature and k represents number of iterations.
(a)
3-point ternary
(b)
3-point quinary
(c)
5-point ternary
(d)
5-point quinary
(e)
7-point ternary
(f)
7-point quinaryPresents comparison among total absolute curvature of 3-point ternary interpolating scheme for different values of parameter. HereL represents total absolute curvature and k represents number of iterations.
(a)
forv2=0.2333
(b)
forv2=0.2888
(c)
forv2=0.3111The total curvature and total absolute curvature are same for a closed convex polygonal curve and both are equal to2π. Hence for a nonconvex curve the measure of deviation (referred as D) from the convex curve can be calculated by subtracting TAC of nonconvex curve from TAC of convex curve that is 2π. In Table 1, we have calculated measure of deviation of convexity of 3-point and 5-point ternary interpolating scheme at different subdivision level. Figure 5 presents graphical representation of measure of deviation of 3-point and 5-point ternary interpolating scheme.Table 1
Measure of deviation of convexity of 3-point and 5-point ternary scheme. Herek presents the level of iteration and D is measure of deviation.
k
Scheme
D
Scheme
D
2
3-point
0.000000
5-point
0.000000
3
⋯
−0.716814
⋯
0.000000
4
⋯
−3.716814
⋯
−0.000001
5
⋯
−8.716814
⋯
−0.000011Presents measure of deviation of convexity of 3-point and 5-point ternary interpolating scheme.
(a)
3-point ternary
(b)
5-point ternary


## 5. Convexity Preservation of Subdivision Scheme

In this section, we discuss condition which guarantee convexity preservation of interpolating scheme. Here we derive conditions for convexity preservation of 5-point ternary interpolating scheme (3.20). Convexity of other schemes can be discussed analogously. We adopt the same procedure as described by [11].


### 5.1. Convexity Preservation of 5-Point Ternary Scheme

Let us suppose that the initial control points are strictly convex, that is,djk>0 (by [12]). For v2=u and v1=u+4/81, the scheme (3.20) for second-order divided differences djk=32k(fj-1k-2fjk+fj+1k) is given by
(5.1)d3ik+1=(49+18u)dik+(19-36u)di+1k+(49+18u)di+2k,d3i+1k+1=-(89+18u)dik+(269+45u)di+1k-(139+36u)di+2k+(49+9u)di+3k,d3i+2k+1=(49+9u)dik-(139+36u)di+1k+(269+45u)di+2k-(89+18u)di+3k.
For simplicity, we put w=4/9+18u, -7/18<w<-1/3, in above three equations, we get (5.2)d3ik+1=wdik+(1-2w)di+1k+wdi+2k,(5.3)d3i+1k+1=-(4+9w9)dik+(32+45w18)di+1k-(5+18w9)di+2k+(4+9w18)di+3k,(5.4)d3i+2k+1=(4+9w18)dik-(5+18w9)di+1k+(32+45w18)di+2k-(4+9w9)di+3k.The conditions which guarantee the convexity preservation are as follows.Theorem 5.1.
Denotepik=di+1k/dik, qik=1/pik=dik/di+1k and let
(5.5)rk=min{pik,qik}.
If the initial control points are all strictly convex, -7/18<w<-1/3 and
(5.6)r0>-2w1+w≜λ,
then the 5-point ternary scheme (3.20), for  v2=w and v1=w+4/81 preserves convexity.Proof.
For convexity preservation it is sufficient to show thatdik>0 and rk>λ. We will use mathematical induction to prove dik>0 and rk>λ. As we know that for k=0, di0>0 and r0>λ by (5.6). Let us suppose that dik>0 and rk>λ. Now we will prove it for k+1. To show dik+1>0, we have to show that d3ik+1>0, d3i+1k+1>0 and d3i+2k+1>0.
From (5.3), we have that
(5.7)d3ik+1=dik(w+(1-2w)pik+wpikpi+1k).
This implies for -7/18<w<-1/3(5.8)d3ik+1>dik{w+(1-2w)λ+wλ2}>0.
From (5.3), we have that
(5.9)d3i+1k+1=dik{-(4+9w9)+(32+45w18)pik-(5+18w9)pikpi+1k+(4+9w18)pikpi+1kpi+2k}.
This implies for -7/18<w<-1/3(5.10)d3i+1k+1>dik(-4+9w9+λ(32+45w)18-5+18w9λ2+λ3(4+9w)18)>0.
Similarly from (5.4), for -7/18<w<-1/3 we have that
(5.11)d3i+2k+1>dik(4+9w18-5+18w9λ+λ2(32+45w)18-4+9w9λ3)>0.
By combining (5.8), (5.10), and (5.11), we have dik+1>0.
Now we proverk+1>λ.
Forp3ik+1=d3i+1k+1/d3ik+1, we get
(5.12)p3ik+1=-(4+9w)/9+((32+45w)/18)pik-((5+18w)/9)pikpi+1k+((4+9w)/18)pikpi+1kpi+2kw+(1-2w)pik+wpikpi+1k.
Now
(5.13)p3ik+1-λ>-(4+9w)/9+λ(32+45w)/18-(5+18w)/9λ2+λ3(4+9w)/18-λ(w+(1-2w)λ+wλ2)w+(1-2w)λ+wλ2.
Since both the numerator and denominator of above expression are positive for -7/18<w<-1/3, therefore
(5.14)p3ik+1-λ>0.
This implies that for -7/18<w<-1/3(5.15)p3ik+1>λ.
For q3ik+1=1/p3ik+1=d3ik+1/d3i+1k+1, we get
(5.16)q3ik+1=wqikqi+1k+(1-2w)qi+1k+w-((4+9w)/9)qikqi+1k+((32+45w)/18)qi+1k-(5+18w)/9+((4+9w)/18)pi+2k.
Now
(5.17)q3ik+1-λ>wλ2+(1-2w)λ+w+(4+9w)/9λ-λ2(32+45w)/18+λ(5+18w)/9-λ2(4+9w)/18-(4+9w)/9λ2+λ(32+45w)/18-(5+18w)/9+λ(4+9w)/18.
Since both the numerator and denominator of above expression are positive for -7/18<w<-1/3, therefore
(5.18)q3ik+1-λ>0.
This implies that for -7/18<w<-1/3(5.19)q3ik+1>λ.
Similarly by taking p3i+1k+1=d3i+2k+1/d3i+1k+1 and by using (5.3)–(5.6), we can easily show that for -7/18<w<-1/3(5.20)p3i+1k+1>λ.
Through the same channel for -7/18<w<-1/3, we have
(5.21)q3i+1k+1>λ.
Similarly for p3i+2k+1=d3i+3k+1/d3i+2k+1 and by using (5.2), (5.4)–(5.6) for -7/18<w<-1/3(5.22)p3i+2k+1>λ.
Through the similar channel for -7/18<w<-1/3, we have
(5.23)q3i+2k+1>λ.
By combining (5.15)–(5.23), we have pik+1, qik+1>λ. Thus rk+1>λ. Since both conditions are satisfied so we concluded that 5-point ternary interpolating scheme (3.20) preserves convexity for v2=u and v1=u+4/81.Finally, we give an example to illustrate our result. Figure6 shows the result after two iteration with u=-11/250. In this figure, the initial control polygon is convex and represented by dotted line and limit curve after two times iterations is represented by solid line and is also convex.Figure 6
Limit  curve after applying 5-point ternary subdivision scheme on initial convex data. Dotted line shows initial convex data and solid line indicates limit curve after two iteration.


## 5.1. Convexity Preservation of 5-Point Ternary Scheme

Let us suppose that the initial control points are strictly convex, that is,djk>0 (by [12]). For v2=u and v1=u+4/81, the scheme (3.20) for second-order divided differences djk=32k(fj-1k-2fjk+fj+1k) is given by
(5.1)d3ik+1=(49+18u)dik+(19-36u)di+1k+(49+18u)di+2k,d3i+1k+1=-(89+18u)dik+(269+45u)di+1k-(139+36u)di+2k+(49+9u)di+3k,d3i+2k+1=(49+9u)dik-(139+36u)di+1k+(269+45u)di+2k-(89+18u)di+3k.
For simplicity, we put w=4/9+18u, -7/18<w<-1/3, in above three equations, we get (5.2)d3ik+1=wdik+(1-2w)di+1k+wdi+2k,(5.3)d3i+1k+1=-(4+9w9)dik+(32+45w18)di+1k-(5+18w9)di+2k+(4+9w18)di+3k,(5.4)d3i+2k+1=(4+9w18)dik-(5+18w9)di+1k+(32+45w18)di+2k-(4+9w9)di+3k.The conditions which guarantee the convexity preservation are as follows.Theorem 5.1.
Denotepik=di+1k/dik, qik=1/pik=dik/di+1k and let
(5.5)rk=min{pik,qik}.
If the initial control points are all strictly convex, -7/18<w<-1/3 and
(5.6)r0>-2w1+w≜λ,
then the 5-point ternary scheme (3.20), for  v2=w and v1=w+4/81 preserves convexity.Proof.
For convexity preservation it is sufficient to show thatdik>0 and rk>λ. We will use mathematical induction to prove dik>0 and rk>λ. As we know that for k=0, di0>0 and r0>λ by (5.6). Let us suppose that dik>0 and rk>λ. Now we will prove it for k+1. To show dik+1>0, we have to show that d3ik+1>0, d3i+1k+1>0 and d3i+2k+1>0.
From (5.3), we have that
(5.7)d3ik+1=dik(w+(1-2w)pik+wpikpi+1k).
This implies for -7/18<w<-1/3(5.8)d3ik+1>dik{w+(1-2w)λ+wλ2}>0.
From (5.3), we have that
(5.9)d3i+1k+1=dik{-(4+9w9)+(32+45w18)pik-(5+18w9)pikpi+1k+(4+9w18)pikpi+1kpi+2k}.
This implies for -7/18<w<-1/3(5.10)d3i+1k+1>dik(-4+9w9+λ(32+45w)18-5+18w9λ2+λ3(4+9w)18)>0.
Similarly from (5.4), for -7/18<w<-1/3 we have that
(5.11)d3i+2k+1>dik(4+9w18-5+18w9λ+λ2(32+45w)18-4+9w9λ3)>0.
By combining (5.8), (5.10), and (5.11), we have dik+1>0.
Now we proverk+1>λ.
Forp3ik+1=d3i+1k+1/d3ik+1, we get
(5.12)p3ik+1=-(4+9w)/9+((32+45w)/18)pik-((5+18w)/9)pikpi+1k+((4+9w)/18)pikpi+1kpi+2kw+(1-2w)pik+wpikpi+1k.
Now
(5.13)p3ik+1-λ>-(4+9w)/9+λ(32+45w)/18-(5+18w)/9λ2+λ3(4+9w)/18-λ(w+(1-2w)λ+wλ2)w+(1-2w)λ+wλ2.
Since both the numerator and denominator of above expression are positive for -7/18<w<-1/3, therefore
(5.14)p3ik+1-λ>0.
This implies that for -7/18<w<-1/3(5.15)p3ik+1>λ.
For q3ik+1=1/p3ik+1=d3ik+1/d3i+1k+1, we get
(5.16)q3ik+1=wqikqi+1k+(1-2w)qi+1k+w-((4+9w)/9)qikqi+1k+((32+45w)/18)qi+1k-(5+18w)/9+((4+9w)/18)pi+2k.
Now
(5.17)q3ik+1-λ>wλ2+(1-2w)λ+w+(4+9w)/9λ-λ2(32+45w)/18+λ(5+18w)/9-λ2(4+9w)/18-(4+9w)/9λ2+λ(32+45w)/18-(5+18w)/9+λ(4+9w)/18.
Since both the numerator and denominator of above expression are positive for -7/18<w<-1/3, therefore
(5.18)q3ik+1-λ>0.
This implies that for -7/18<w<-1/3(5.19)q3ik+1>λ.
Similarly by taking p3i+1k+1=d3i+2k+1/d3i+1k+1 and by using (5.3)–(5.6), we can easily show that for -7/18<w<-1/3(5.20)p3i+1k+1>λ.
Through the same channel for -7/18<w<-1/3, we have
(5.21)q3i+1k+1>λ.
Similarly for p3i+2k+1=d3i+3k+1/d3i+2k+1 and by using (5.2), (5.4)–(5.6) for -7/18<w<-1/3(5.22)p3i+2k+1>λ.
Through the similar channel for -7/18<w<-1/3, we have
(5.23)q3i+2k+1>λ.
By combining (5.15)–(5.23), we have pik+1, qik+1>λ. Thus rk+1>λ. Since both conditions are satisfied so we concluded that 5-point ternary interpolating scheme (3.20) preserves convexity for v2=u and v1=u+4/81.Finally, we give an example to illustrate our result. Figure6 shows the result after two iteration with u=-11/250. In this figure, the initial control polygon is convex and represented by dotted line and limit curve after two times iterations is represented by solid line and is also convex.Figure 6
Limit  curve after applying 5-point ternary subdivision scheme on initial convex data. Dotted line shows initial convex data and solid line indicates limit curve after two iteration.


## 6. Conclusion

In this paper, we offered an explicit general formula to generate the mask of odd-pointsn-ary interpolating symmetric schemes for any odd n⩾3. From this formula one can easily generate the mask of odd-points, lower and higher arity interpolating schemes with and without free parameters. Moreover, odd-point n-ary schemes of Hassan and Dodgson [7], Zheng et al. [8], Lian [3, 9] are special cases of our proposed explicit formula. Moreover, we have concluded that error bounds between limit curve and control polygon of subdivision scheme at k-th level decreases with the increase of arity of the scheme. We also noticed that error bound is directly proportional to the number of points involved to insert new point in the control polygon (i.e., complexity of the scheme). We also calculated total absolute curvature for subdivision schemes having different arity and different complexity. We have concluded that total absolute curvature is directly proportional to arity and inversely proportional to complexity of the scheme. Convexity preservation is an important geometrical property of subdivision scheme. Therefore we discussed the convexity of some of our scheme. Convexity of other schemes can be discussed analogously.



---

*Source: 205863-2012-11-07.xml*