Open Journal of Applied Sciences, 2013, 3, 106-111
doi:10.4236/ojapps.2013.31B1022 Published Online April 2013 (http://www.scirp.org/journal/ojapps)
The 4-Point α-Ary Approximating Subdivision Scheme
Abdul Ghaffar1, Ghulam Mustafa1, Kaihuai Qin2
1Department of Mathematics, The Islamia University of Bahawalpur, Bahawalpur, Pakistan
2Dept. of Computer Science & Technology, Tsinghua University, Beijing 100084, P. R. China
Received 2013
ABSTRACT
A general formula for 4-point

-Ary approximating subdivision scheme for curve designing is introduced for any ar-
ity 2

. The new scheme is extension of B-spline of degree 6. Laurent polynomial method is used to investigate the
continuity of the scheme. The variety of effects can be achieved in correspondence for different values of parameter.
The applications of the proposed scheme are illustrated in comparison with the established subdivision schemes.
Keywords: Approximating Subdivision Scheme; Binary; Ternary;

-Ary; Continuity; Convergence and Shape
Parameters
1. Introduction
Subdivision modeling methods are effective algorithms
to generate continuous curves and surfaces from a dis-
crete set of control points by subdividing them according
to some refining rules, recursively. Repetition of this
process produces a very good approximation to the curve
or surface defined by the original set of control points. In
recent years, the subject of subdivision gained popularity
due to some new applications, such as in the 3D anima-
tion industry. The next venture is to introduce these
methods to be more consistent and efficient to the world
of geometric modeling in the industry.
Approximating schemes were first developed by Rham
and Chaikin [1,2]. Consequent to this, a lot of work has
been done by different authors in the field of binary sub-
division schemes, but the research communities are in-
terested in introducing higher arity schemes (i.e. ternary,
quaternary, ...n-ary) which give better result and less
computational cost.
In late 80,s with the help of wavelet theory, a relation-
ship between subdivision scheme and the “mask” of re-
finable function have been developed. Lian [3,4] has
introduced 3, 4, 5 and 6-point a-ary interpolating
schemes. In these research papers, Lian used wavelets
theory, a relatively new subject area that has been deeply
studied for the last two decades or so, and found many
successful applications. Lian [5] also offered 2m and (2m
+ 1) -point interpolating a-ary schemes for curve design-
ing. In 2009, Mustafa and Khan [6] for the first time in-
troduced a new 4-point quaternary approximating subdi-
vision scheme. Mustafa and Najma [7] presented same
perspective for constructing (2b + 2) and (2b + 4) -point
n-ary interpolating and approximating schemes. Ghaffar
et al. presented unified 3-point

-ary approximation
schemes and discussed various properties [8]. This moti-
vates us to present 4-point

-ary approximating scheme
with high smoothness and more degree of freedom for
curve designing. One of the main objectives of current
work is to extend “The B-Spline of degree 6” to 4-point

-ary approximating subdivision scheme.
This paper is organized as follows: General form of
4-point

-ary subdivision scheme is constructed in Sec-
tion 2. The family of 4-point

-ary approximating
scheme, basic properties and analysis are presented in
Section 3. Comparison of 4-point

-ary schemes is
given in Section 4. Finally conclusion is given in Section
5.
2. Main Results
In this section, we are introducing family of 4-point

-ary approximating subdivision scheme for curve de-
signing for any arity 2

. This family is the extension
of B-spline of degree six i.e. (4-point approximating sub-
division scheme):
1
21 1
1
2111 2
735211
,
6464 6464
121357
.
6464 6464
kkkk
iiii
kkkk
iiii
2
k
i
k
i
f
ffff
f
ffff



 









,
(1)
If there exist a unique −sequence that de-
scribes the “two scale equation”
2
l{}
k
P
 
2
k
k
x
Pxk 



 (2)

A. GHAFFAR ET AL. 107
of scaling function

. Then corresponding to this -
sequence, let us introduce the notation
2
l

1
() ,
2
k
k
k
PzP zPz




 (3)
Due to the development of the wavelet theory, the
schemes (1) can be easily re-discovered by the scaling
functions 4

satisfying the two-scale equations
   
 
 
444 4
444
44
127 212122
64
352335242125
72627,
ttt t
tt
tttR
 
   
   

t
(4)
By taking the Fourier transforms of (4), we arrive at
the following two-scale equations of 4


2
444
3
2
2
44
5
3
2
44
11 721
ˆˆˆ ˆ
64 222222
35 35
ˆˆ
2222
21 7
ˆˆ
2222
iw
iw
iw
iw
iw
iw
ww
wee
ww
ee
ww
ee
 
 
 
 
 

 
 
 
 
 








4
w
7
2
4
1ˆ.
22
iw w
e




 

This implies
 
4
2
2
3
2
44
3
0
2
13
11
ˆˆ.
22
41
iw
j
iw
iw
j
e
w
we
j
e





 

 
 


 
 
 




This normalization simplifies to the following Fourier
transform formulation:
 
444
1
ˆˆ ,
22
w
wP



 z
where
 
4
23
43
0
3
11 ,
1
4
j
j
z
Pz z
j z
 





 (5)
and 2.
iw
ze
By introducing the shape parameter in (5), we get
j
u
 
4
23
42
0
3
111.
14
4
j
j
j
z
Pz uz
j z





 (6)
By taking and , we
get
03
4uu w 12 4(1 )uu w 
2
4
4
1(1 )
()()(1 )(1 ).
16 (1)
z
Pzwwzwzwz
z



Now, if we allow the scaling factor, denoted by a, to
be , and denote such a scaling function denoted by 2
a

, then the Fourier transforms of two-scale equation of
a

becomes



,
iw
aaa aw
wP
a




 
 
e
and




.
aaa
w
wP
a



 z
where and again, is its two-scale symbol
and
(/)iw a
zeaP
a

is then equivalent to satisfies
aP
42
43
1(1 )
()()(1)(1 ).
(1 ) (2)
a
az
PZwwzwzwz
z a



3

(7)
3. Family of 4-Point a-Ary Schemes
In this section, we discuss only three 4-point schemes.
For setting 2,3a

and 4 in (7), we obtain three poly-
nomials


a
Pza
4 with following sets of coef-
ficients called the mask of the 4-point binary, ternary and
quaternary schemes, respectively.
,2,3,4
2
4
,13 ,5,105 ,
1,
105 ,5,13, 16
www w
ww ww









(8)
3
4
,13,55,143,263,
1359 ,359,263,143,,
54 55,13,
ww www
wwww
www

 











(9)
and
4
4
,13 ,55 ,147 ,305 ,
51,717,8413 ,8413,
1,
717 ,51,305,147 , 128
55,13,
ww www
wwww
www w
www

 




 












(10)
Order of continuities of the above schemes is given in
Table 1. One can easily find the order of continuity over
the parametric intervals by using the approach of [9].
3.1. Support of Basic Limit Function
The basic function of a subdivision scheme is the limit
function of the proposed scheme for the following data
01, 0,
0, 0.
i
i
fi



 (11)
2 3

The following theorem is related to the support of ba-
sic limit functions of the 4-point a-ary scheme.
Theorem 1. The basic limit functions of 4 pro-
posed 4-point a-ary approximating schemes have support
Φ
a

A. GHAFFAR ET AL.
108
Table 1. The order of continuity of proposed 4-point a-ary schemes for certain ranges of parameter.
Scheme Parameter Cn Scheme Parameter Cn
Binary 35
22
w C0 Quaternary 33 14 2 w C0
... 35
22
w C1 ... 1319
22
w C1
... 13
22
w C2 ... 35w

 C2
... 13
22
w C3 ... 13w

 C3
01w C4
... 1
4
w C5
Ternary 23 31
44
w C0
... 71
22
w
1
C1
... 24w C2
... 13w C3
(a) (b) (c)
Figure 1. (a-c) represent the basic limit functions of the 4-point binary, ternary and quaternary schemes, respectively.
by 411
2
a
a


on both sides. Hence after k subdivision width 41
1
a
sa

, for which implies
2, 3,4,...,,am
that it vanishes outside the interval

4141
,
2121
aa
aa








.
steps the furthest non-zero vertex on the left will be at
2
1
0
41111
2
41 1
.
k
k
j
j
a
aaa
a
aa


















Proof. Since the basic function is the limit function of
the scheme corresponding to (7) for the data (11), its
support width “s” can be determine by computing how
far the effect of the non-zero vertex 0
0
f
will propagate
along by. As the mask of a-ary 4-point scheme is 41a

long sequence by centering it on that vertex; the dis-
tances to the last of its left and right non-zero coefficients
So the total support width is

0
411 41
2.
1
j
j
aa
aa a





 

 



are equal to 41
2
a At the first subdivision step we see
3.2. Precision Set
that the vertices on the both sides of 1
0
f
at 41
2
a

are For approximating schemes, we do not expect new verti-
ces to be lie on the same curve as old ones, so it is nec-
essary to look to see whether all the vertices lie on a
common curve. We can calculate the order of precision
by using the technique as given in [10].
the furthest non-zero new vertices. At each refinement,
the distances on both sides are reduced by the factor 1
a.
At the next step of the scheme, this will propagate along

A. GHAFFAR ET AL. 109
Lemma 2. The scheme (3.1) has cubic precision.
Proof. We carry out this result by taking our origin the
middle of an original span with ordinate

,5,3,1,1,3,5,
nnnnnn
  
If n
y
x, then we have

 
 
  

 
1234
4321
1111
4321
4321
,531 1
5311,
3113,
3113,
,
1135,
nnn
nnnn
nnnn
nnnn
nn nn
ya aa a
aaaa
aaaa
aaaa
aaaa
 

 
 
 

,
n
where
1234
375
,,,
1616 1616
aaaa
1
.
If 1
y
x, then we have


2
531135
,,,,,,,
2 22222
,1,1,1,1,1,
0,
y
y
y


 
 



where

represents the differences of the vertices.
If 2
y
x, then we have

15 73 3
, 2,2,2,2
2 222
715
2,2,
22
y wwww
ww


,
Taking further differences, we get .
30y




If 3
y
x, then we have

,2515,9 9,22,
22,99,2515,
yww
ww w
 
 
w
by taking further differences, we get .
4
δy0t 

Thus the scheme has cubic precision.
For this analysis we observe that the scheme (8) is de-
signed so that it has cubic precision for any value of .
While the schemes (9) and (10) have cubic precision for
w
any value of w and with the special values 1
w3

and
1
w
2
, the schemes have quartic precision, respectively.
4. Comparison and Application
In this section, we show that the popular existing schemes
are special cases of our proposed family of schemes (8)-
(10).
 With the special values of parameter (w0

and
1
w4

), the subdivision schemes generated by B-splines
of degree 4 and 6, respectively, are obtained from the
schemes (8).
 Moreover, the proposed scheme (8) is a generalized
scheme, as the mask of the proposed scheme coincides
with the mask of schemes [9,11-13] after setting 5 w,
8


1
w0,wω
6

 and wu

respectively.
 It may be noted that if we put
11
wω,w u
6162
 
1
3
and
35
w24 
in (9), the proposed 4-point scheme can also be consid-
ered as the general form of the stationary 4-point ternary
approximating schemes of [8,13,16], respectively.
 For substituting 21 w8

 , the obtained mask of
scheme (10) coincides with mask of the famous 4-point
quaternary scheme of Ko [17].
Here we compare our proposed schemes with the ex-
isting binary, ternary and quaternary schemes (see Table
2). It is observed that the continuity and approximation
order of proposed schemes are better than the existing
schemes. Moreover, Figure 2 is exposed to show the role
of free parameters when the schemes (8)-(10) applied on
discrete data points. In Figure 2(a), black, red and blue
lines show the visual smoothness of the binary scheme
at the parametric values 1
0, 8 ww and 1
2
w

, re-
spectively. In Figure 2(b), blue, green, black and red
lines show the visual smoothness of the ternary scheme
at the parametric values 1
1,, 0
2
ww w, and
1
2
w

, respectively. In Figure 2(c), blue, green,
black and red lines show the visual smoothness of the
quaternary scheme at the parametric values 1,w


1,
2
ww 0

 and 1
2
w

, respectively. From Figure
2, we conclude that the behavior of the limiting curve
acts as tightness/looseness when the values of free pa-
ameter vary. r

A. GHAFFAR ET AL.
110
Table 2. Comparison of 4-point ternary schemes.
Type Support Scheme Order Cn
Binary 4-point [18] Inteng rpolati6 4 1
Binary 4-point [19] Interpolating 4 6 1
Binary 4-point [12] Approximating 7 4 2
Interpolating Ternary 4-point [20] 5 4 1
Interpolating 5 3 Ternary 4-point [21, 3] 1
Interpolating Ternary 4-point [22] 5 2
Interpolating 5 Ternary 4-point [3] 3 1
Ternary 4-point [16] Approximating 4 5.5 2
Approximating 5 4 Quaternary 4-point [17] 2
Approximating 4 Quaternary 4-point [6] 5 3
Approximating 7 3 Binary 4-point proposed 5
Approximating 5 Ternary 4-point proposed 5.5 3
Approximating 5 5 Quaternary 4-point proposed 3
(a) (b) (c)
Figure 2. ectively.
. Conclusio
oint a-ary approximating schemes for
027), the National Natural
a (60973101) and HEC Paki-
G. de Rham, “Un Peude Mathematiques a Proposed Une
Courbe Plane,” Revwede Mathematiques Elementry II,
Oevred Comp
(a-c) show the role of shape parameter of the schemes (8), (9) and (10) resp
5ns 6. Acknowledgement
The families of 4-p
curve design were established in general. The first family
is binary, the second is ternary and the third family is
quaternary approximating. The support of subdivision
scheme influences the locality. One of the best ways to
get a smaller support is to raise the arity. This is one of
the advantages of the proposal of the scheme. We have
also studied its continuity and determined its order of
precision. It is observed that the order of precision set
increases by increasing the arity of the schemes while the
continuity decreases by increasing the arity of the
scheme. Moreover, we have showed that several previ-
ously proposed schemes are members of this family. It
has been shown that proposed schemes are better than
existing schemes in the sense of smoothness and ap-
proximation order.
This work is supported by the Beijing Municipal Natural
Science Foundation (4102
Science Foundation of Chin
stan.
REFERENCES
[1]
letes, 1947, pp. 678-689.
[2] G. M. Chaikin, “An Algorithm for High-Speed Curve
Generation,” Computer Graphics and Image Processing,
Vol. 3, No. 4, 1974, pp. 346-349.
doi:10.1016/0146-664X(74)90028-8
[3] J. -A. Lian, “On A-ary Subdivision for Curve Design: I.
4-point and 6-point Interpolatory Schemes,” Applications

A. GHAFFAR ET AL. 111
and Applied Mathematics: An Inte
3, No. 1, 2008, pp.18-29.
rnational Journal, Vol.
7.
p. 434-444.
[4] J. -A. Lian, “On A-ary Subdivision for Curve Design: II.
3-point and 5-point Interpolatory Schemes,” Applications
and Applied Mathematics: An International Journal, Vol.
3, No. 2, 2008, pp. 176-18
[5] J. -A. Lian, “On a-ary Subdivision for Curve design: III.
2m-point and (2m+1) point Interpolatory Schemes,” Ap-
plications and Applied Mathematics: An International
Journal, Vol. 4, No. 2, 2009, p
[6] G. Mustafa and F. Khan, “A New 4-point Quaternary
Approximating Subdivision Scheme,” Abstract and Ap-
plied Analysis, Vol. 2009, Article ID 301967, 14 pages.
[7] G. Mustafa and A. R. Najma , “The Mask of (2b +
4)-point n-ary Subdivision Scheme,” Computing, Vol. 90,
No. 1-2, 2010, pp. 1-14. doi:10.1007/s00607-010-0108-x
[8] A. Ghaffar, G. Mustafa and K. Qin, “Unification and
Application of 3-point Approximating Subdivision
Schemes of Varying Arity,” Open Journal of Applied
Sciences, Vol. 2, No. 4B, 2012, pp. 48-52.
doi:10.4236/ojapps.2012.24B012
[9] M. F. Hassan and N. A. Dodgson, “Ternary and
Three-point Univariate Subdivision Schemes,” In: A.
Cohen, J. L. Marrien, L. L. Schumaker (Ed
Surface Fitting: Sant-Malo2002, N
s.), Curve and
ashboro Press, Brent-
nger, 2002, pp. 51-68.
wood, 2003, pp. 199-208.
[10] N. Dyn, “Analysis of Convergence and Smoothness by
the Formalism of Laurent Polynomials,” In: A.Iske, E.
Quak, M. S Floater (Eds), Tutorials on Multiresolution in
Geometric Modelling, Spri
doi:10.1007/978-3-662-04388-2_3
[11] G. Mustafa, F. Khan and A. Ghaffar, “The -Point Ap-
proximating Subdivision Scheme,” Lobachevskii Journal
of Mathematics, Vol. 30, No. 2, 2009, pp. 138-145.
doi:10.1134/S1995080209020061
[12] N. Dyn, M. S. Floater and K. Horman, “A Four-Point
Subdivision Scheme with Fourth Order Accuracy and its
Extension,” In Mathematical Methods for Curves and
Surfaces: Tromso 2004, M. Daehlen, K. Morken, and L
ring, 2009, pp.
.
L. Schumaker (eds.), 2005, pp. 145-156.
[13] H. Zheng, M. Hu and G. Peng, “P-ary Subdivision Gen-
eralizing B-splines,” Second International Conference:
On Computer and Electrical Enginee
214-218. doi:10.1109/ICCEE.2009.204
[14] A. Ghaffar and G. Mustafa, “A Family of Even-Point
ternary Approximating Schemes,” ISRN Applied Mathe-
matics, Vol. 2012, 2012, Article ID 197383, 14 pages.
er-
[15] H. Zheng, M. Hu and G. Peng, “Ternary Even Symmetric
2n-point Subdivision,” International Conference on:
Computational Intelligence and Software Engine
ing,2009, pp. 1-4.doi:10.1109/CISE.2009.5363033
[16] K. P. Ko, B. -G. Lee and G. Joon Yoon. “A Ternary
4-point Approximating Subdivision Scheme,” Applied
Mathematics and Computation, Vol. 190, 2007
[17] K. P. Ko, “A Quatnary Approximating 4-point Subdivi-
sion Scheme,” J. KSIAM, Vol. 13, No. 4, 2009, PP.
307-341.
[18] C. Beccari, G. Casciola and L. Romani, “A
Non-stationary Uniform Tension Controlled Interpolating
4-point Scheme Reproducing Conics,” Computer Aided
Geometric Design, Vol. 24, No. 1, 2007, pp. 1-9.
[19] G. Casciola and L. Romani. “An Interpolating 4-point
Ternarynon-stationary Subdivision Scheme with Tension
Control,” Computer Aided Geometric Design, Vol. 24,
. 1, 2009, pp. 916-927.
No. 2, 2007, pp. 210-219.
[20] G. Casciola and L. Romani, “Shape Controlled Interpola-
tory Ternary Subdivision,” Applied Mathematics and
Computation, Vol. 215, No
[21] G. Deslauriers and S. Dubic, “Symmetric Iterative Inter-
polation Process,” Constractive Approximation, Vol. 5,
No. 1, 1989, pp. 49-68. doi:10.1007/BF01889598
[22] M. F. Hassan, I. P. Ivrissimitzis, N. A. Dodgson and M. A.
Sabin, “An Interpolating 4-points C2 Ternary Stationary
Subdivision Scheme,” Computer Aided Geometric Design,
Vol. 19, 2002, pp. 1-18.