Unification and Application of 3-point Approximating
Subdivision Schemes of Varying Arity
Abdul Ghaffar*, Ghulam Mustafa
Department of Mathematics
The Islamia University of Bahawalpur
Bahawalpur, PAKISTAN
*gulzarkhan143@yahoo.com,
Beijing 100084, P. R. CHINA
†ghulam.mustafa@iub.edu.
pk
Kaihuai Qin
Dept. of Computer Science & Technology
Tsinghua University
Corresponding author: E-mail: qkh-dcs@tsinghua.edu.cn
Abstract—In this paper, we propose and analyze a subdivision scheme which unifies 3-point approximating subdivision
schemes of any arity in its compact form and has less support, computational cost and error bounds. The usefulness of the
scheme is illustrated by considering different examples along with its comparison with the established subdivision schemes.
Moreover, B-splines of degree 4and well known 3-point schemes [1, 2, 3, 4, 6, 11, 12, 14, 15] are special cases of our
proposed scheme.
Keywords-component; Approximating subdivision scheme; binary; ternary; -ary; continuity and Laurent polynomial
MSC (2000): 65D17, 65D07, 65D05.
1. Introduction
In recent years, subdivision schemes has becomeone of
the most popular methods of creating geometric objects in
computer aided geometric design and animation industry.
Their popularity is due to the facts that subdivision
algorithms are easy to implement and suitable for computer
applications. Subdivision schemes can be classified into
approximating and interpolating ones.
The beginning of the subdivision story can be dated back
to the papers of Chaikin [2] over thirty years ago, but the
idea of families of subdivision schemes of higher arity is
relatively new. Based on wavelet theory, Lian [8]
introduced 2݉െpoint ܽ-ary for any ܽ2 and (2݉ +
1) െpoint ܽ-ary for any odd ܽ3 interpolatory subdivision
schemes for curve design. These schemes include the
extended family of the classical 4- and 6-point interpolatory
Į-ary schemes [9] and the family of the 3- and 5-point ܽ-
aryinterpolatory schemes [10]. Mustafa and Khan [7]
offered a new 4-point quaternary approximating subdivision
scheme. Siddiqi and Rehan [15] introduced a modified form
of binary and ternary 3-point subdivision schemes which are
C1and ܥ2 in the intervals െ1
8,1
5and െ1
72,7
72respectively.
Most work in the area of subdivision schemes has
considered binary and ternary schemes. But the research
communities are gaining interest in introducing higher arity
schemes (i.e. ternary, quaternary,…,݊-ary) that give better
results and less computational cost. This motivates us to
present the family of schemes with higher arity and more
degree of freedom for curve designing. We decided to
investigate schemes with an odd number of control points,
specifically 3-point schemes. This led to a more general
investigation of higher arity subdivision schemes.
In this paper 3-point subdivision schemes are extended to
Į-ary 3-point approximating subdivision schemes for any
integer ܽ൒2.In ܽ-ary 3-point approximating subdivision
schemes, we introduced new families of subdivision
schemes for curve design. The first family is binary
approximation, second is ternary approximation and onto ܽ-
ary approximation. A general formula for the mask of ܽ-ary
3-point approximating subdivision scheme is defined as
follows
Ƚ3
ܽ(ݖ)=1
()21െݖܽ
1െݖ3൭෍൬2݅൰ݖ݅
2
݅=0൱, (1)
where “ܽ” represents the arity.
In this paper we recall basic definitions and preliminary
results in Section II. The family of ܽ-ary 3-point
approximating scheme is presented in Section III.
Comparison with the existing 3-point scheme, basic
properties of the limit function, error analysis and effect of
parameters ܽ-ary 3-point schemes are discussed in Section
IV. Conclusion isalso discussed in Section IV.
I. ANALYSIS OF THE GENERAL ܽെARY SCHEME
A general form of univariatea-ary subdivision scheme S
which maps a polygon
^`
=
i
i
kk
ff
to a refined polygon
^`
Zi
k
i
k
ff
1
1
is defined by
݂݅݇+1=෍ߙ݆ܽെ݂݆݅݇, ݅אܼ (2
݅אܼ )
where the set ߙ={ߙ݅:݅אܼ}of coefficients is called the
mask at ݇-th level of refinement. Anecessary condition for
the uniform convergence of subdivision scheme (2) is
Open Journal of Applied Sciences
Supplement2012 world Congress on Engineering and Technology
48 Cop
y
ri
g
ht © 2012 SciRes.
෍ߙ݆ܽ=
݅אܼ ෍ߙ݆ܽ+1=
݅אܼ ෍ߙ݆ܽ+2=
݅אܼ …෍ߙ݆ܽ+ܽെ1=
݅אܼ 1. (3)
A subdivision scheme is uniformly convergent if for any
initial data ݂0 = {݂݅0: ݅אܼ}, thereexistsa continuous
function ݂ such that for any closed interval ܫ ؿ ܴ, it
satisfies ݈݅݉
݇՜λݏݑ݌
݅אܽ݇ܫ|݂݇െ݂(ܽെ݇݅)|=0.
Obviously, ݂ = ܵλ݂0.
Introducing a symbol called Laurent polynomial
ߙ(ݖ)=෍ߙ݅ݖ݅
݅אܼ , (4)
of the mask ߙ={ߙ݅:݅אܼ} which play an efficient role to
analyze the convergence andsmoothness of subdivision
scheme. From (3) and (4) the Laurent polynomial of
convergentsubdivision scheme satisfies
ߙ൫݁4݄݅ ߨ/ܽ൯=0, ݄אܼת (0,ܽ)andߙ(1)=ܽ. (5)
This condition guarantees the existence of a related
subdivision scheme for the divided differencesof the original
control points and the existence of an associated Laurent
polynomial Į(ݖ)
ߙ(1)(ݖ)=ܽݖܽെ11െݖ
1െݖܽ൰ߙ(ݖ).
The subdivision scheme ܵ1 with Laurent polynomial ߙ(1)(ݖ),
is related to the scheme ܵ withLaurent polynomial ߙ(ݖ) by
the following theorem.
Theorem 1[5] Letܵdenote a subdivision scheme
with Laurent polynomial ߙ(ݖ)satisfying (5). Then there
exists a subdivision scheme ܵ1with the property
ο݂݇1ο݂݇െ1,
where݂݂݇݇0and ο݂݇={(׏݂݇)݅݇൫݂݅+1
݇െ݂݅݇൯; ݅א
ܼ}. Furthermore, ܵis a uniformlyconvergent if and only if
1
ܵ1converges uniformly to zero function for all initial data݂0,
in the sense thatlim
݇՜λ1
ܽܵ1݂݇0=0.
The above theorem indicates that for any given scheme ܵ,
with the mask Į satisfying (3), wecan prove the uniform
convergence of ܵ by deriving the mask of
1
ܽܵ1and
computing ฯቀ1
ܽܵ1݅λfor ݅ = 1,2,3...,ܮ, where ܮ is the
first integer for whichฯቀ 1
ܽܵ1ܮλ<1.If such an ܮ
exists,then ܵ converges uniformly. Since there are ܽ rules for
computing the values at the nextrefinement level, so we
define the norm
ԡܵԡλ
=݉ܽݔ൝෍หߙ݆ܽห,
݅אܼ ෍หߙ݆ܽ+1
݅אܼ ,෍หߙ݆ܽ+2
݅אܼ ,…,෍หߙ݆ܽ+ܽെ1
݅אܼ ൡ, (6)
and
ብ൬1
ܽܵ1ܮλ=݉ܽݔ൝෍ቚܾ݅+ܽܮ
݊,ܮ ݆ቚ;݅
݅אܼ
=0,1,2,…,ܽܮെ1,(7)
where ܾ[݊, ܮ]=1
ܽܮෑߙ(݊)ቀݖ݆ܽ
ܮെ1
݆=0 , (8)
and ߙ(݊)(ݖ)=ܽݖܽെ11െݖ
1െݖܽ൰ߙ(݊െ1)(ݖ)
=ܽݖܽെ11െݖ
1െݖܽ൰ߙ(ݖ),݊൒1.
Definition 1. The number of points inserted at the level
݇ + 1
between two consecutive points from a level
݇
is
called arity of the scheme. In the case when number of
points inserted are
2,3,...ܽ,
the subdivision schemes are
called binary, ternary,...,
ܽ
-ary, respectively.
Figure 1: (a), (b) and (c) represent binary, ternary and
quaternary refinement of coarse polygons using (1) for
݊ = 2,3,4,
respectively.
2. Family of the general ܉-ary 3-point
approximating scheme
In this section, we are introducing a family of 3-point
ܽ
-
ary approximating subdivision schemes for curve design
for any integer
ܽ
ı 2, which is an extension of “B-spline”.
We have proved this family by using Chaikin [2], Hassan
and Dodgson [4]. The Chaikin’s algorithm for curve
design introduced in 1974 is given by
݂
݇+1=3
4݂݅݇+1
4݂݅+1
݇,
݂
݇+1=1
4݂݅݇+3
4݂݅+1.
݇
(9)
About twenty seven years later, it was extended to the 3-
point scheme by Hassan and Dodgson and is given by
݂
݇+1=5
16݂݅െ1
݇+10
16݂݅݇+1
16݂݅+1
݇,
݂
݇+1=1
16݂݅െ1
݇+10
16݂݅݇+5
16݂݅+1.
݇
(10)
The Laurent polynomials of (9) and (10) are
ߙ22(ݖ)=1
41െݖ 2
1െݖ2σ1݅൯ݖ ݅
1
݅=0 ൯,
ߙ32(ݖ)=1
161െݖ2
1െݖ3σ2݅൯ݖ ݅
2
݅=0 ൯.
(11)
If “
ܽ
” represents the arity, then by generalizing, we get
Cop
y
ri
g
ht © 2012 SciRes.49
Ƚ3
ܽ(ݖ)=1
()21െݖܽ
1െݖ3൭෍൬2݅൰ݖ݅
2
݅=0 ൱. (12)
where integers ܽ൒2. From the coefficients of Laurent
polynomial (12), we get the mask Ƚ3
ܽof family of 3-point ܽ-
ary approximating subdivision schemes for curve design for
any integerܽ ൒ 2.
By adjusting the shape parameter in eq (12), we get the 3-
point ܽ-ary parametric approximatingsubdivision scheme
Ƚ3
ܽ(ݖ)=1
()21െݖܽ
1െݖ3൭෍൬2݅൰ߤ݅ݖ݅
2
݅=0 ൱, (13)
and
ܽ
222݅൰ߤ݅=ܽ,ߤ݆2െ݆, ݆=0,1. (14)
2
݅=0
From the coefficients of Laurent polynomial (13) and
using (14), we get the mask Ƚ3
ܽ of afamily of the 3-point ܽ-
ary parametric approximating subdivision schemes for curve
design forany integer ܽ ൒ 2.
Remark:For a = 2, 3, 4, in (12), we get the mask of the
following 3-point binary, ternary and quaternary schemes,
re spec t iv ely,
ە
۔
ۓ
Ƚ3
ܽ=1
16{1,5,10,10,5,1},
Ƚ3
ܽ=1
36{1,5,13,22,26,22,13,5,1},
Ƚ3
ܽ=1
64{1,5,25,38,46,46,38,25,5,1}.
For a = 2, 3, 4, in (12) and using (13) we get the mask of the
following 3-point binary, ternary and quaternary schemes,
respectively,
ە
ۖ
۔
ۖ
ۓ
ߙ3ܽ=1
16{ߤ0,4+ ߤ0,12െ2ߤ0,12െ2ߤ0,4+ߤ00},
ߙ3ܽ=1
36ߤ0,4 +ߤ0,12+ߤ0,24െ2ߤ0,28െ2ߤ0,
24െ2ߤ0,12+ߤ0,4+ߤ00ൠ , (15)
ߙ3ܽ=1
64ߤ0,4+ߤ0,12+ߤ0,24+ߤ0,40െ2ߤ0,48 െ2ߤ0,
40െ2ߤ040െ2ߤ0,24+ߤ0,12+ߤ0,4+ߤ00ൠ.
3. Comparison with existing
approximating schemes
In this section, we will show that the popular existing
Chaikin scheme and 3-point schemes arespecial cases of our
proposed family of schemes. Here we will also present
support of the basiclimit function and compare the error
bounds between the limit curve and the control polygonafter
the ݇-fold subdivision of the 3-point schemes.
A.Special cases
Here we see that the existing symmetric schemes are the
special cases of our scheme (15).
xBy takingߤ0 = 0,ߤ0= െ48߱,ߤ0 = 1,ߤ0 =
3
20 =2
3+ 4߱,ߤ0 = 1/2and ߤ0 = െ3
2+
16ߤ in ߙ32, we get the 3-point binary scheme of
[2,3,4,6,11,14,15], respectively
xBy settingߤ0= ݑ–1
3, ߤ0 =4
30 = െ4,ߤ0 =
1/3 + 4߱ and ߤ0 = 1/2 + 36ߤ in ߙ33, we get
the 3-point ternary scheme of Aslam et al. [1, 4, 10,
15], respectively.
B.Support of basic limit function
The basic function of a subdivision scheme is the limit
function of the proposed scheme forthe following data
݂݅0=ቄ1, ݅=0,
0, ്݅0. (16)
Theorem 2.The basic limit functions of ܽ߶3 proposed ܽ-ary
3-point approximating schemes have support width ݏ =
3ܽെ1
ܽെ1,
forܽ = 2,3,4,...,݉, which implies that it vanishes outside
theinterva lቂെ3ܽെ1
2(ܽെ1),3ܽെ1
2(ܽെ1).
Figure 2: In this figure (a), (b), and (c) represent the basic
limit functions of 3-point binary, ternary andquaternary
schemes, respectively.
C.Error bounds
In Table 1 by using [13], with ߯ = 0.1, we have computed
the error bounds between limit thecurve and the control
polygon after the ݇-fold subdivision of the 3-point schemes.
It is clearfrom Table 1 and Fig. 3 that the error bounds of the
3-point schemes (13) at each subdivisionlevel decrease by
increasing the arity of the schemes. Moreover, the support,
computationalcost and error bounds of higher arity schemes
are better than the lower arity schemes.
TABLE 1: ERROR BOUNDS OF 3-POINT SCHEME WITH VARYING ARITY:
k/a1 23 45
binary0.075000 0.0375000.018750 0.0093750.004687
ternary 0.033333 0.011111 0.003704 0.001235 0.000412
quaternary 0.020833 0.005208 0.001302 0.000326 0.000081
Figure 3: Comparison: Error bounds between the ݇-th level
control polygons and the limitcurves of 3-point schemes of
varying arity.
4. Effects of parameters in proposed
We will discuss the three major effects/upshots of parameter
in schemes (13). Effects ofparameters in other schemes can
be discussed analogously.
D. Continuity
50 Cop
y
ri
g
ht © 2012 SciRes.
The effects/upshots of the parameter u in schemes (3.7) on
order of continuity are shown inTable 2. One can easily find
the order of continuity over the parametric intervals by using
theapproach of [5].
TABLE 2:THE ORDER OF CONTINUITY OF PROPOSED 3-POINT BINARY,
TERNARY AND QUATERNARY APPROXIMATING SCHEMES FOR CERTAIN
RANGES OF THE PARAMETER:
SchemeParameter ܥ݊Scheme Parameter ܥ݊
binary െ2൑ߤ0൑6 0
Cternary െ6൑ߤ0൑12
0
C
…….. െ1൑ߤ0൑3
1
C
……… െ4൑ߤ0൑8
1
C
…….. 0൑ߤ0൑2 2
C……… 0൑ߤ0൑4
2
C
…….. ߤ0=1 3
C
quaternary െ12൑ߤ0൑20 0
C
……… െ6൑ߤ0൑10
1
C
……… 0൑ߤ0൑4
2
C
E.Shapes of limit curves
In Figure 4 the effect of the parameter in (13) on the graph
and continuity of the limit curveis shown. This figure is
exposed to show the role of the free parameter when 3-point
schemes(14) applied on discrete data points. From these
figures, we see that the behavior of thelimiting curve acts as
tightness/looseness when the values of free parameter vary.
Figure 4: The initial polygons and effect of the parameter
on limit curves of the 3-point binary, ternary and
quaternary schemes.
F.Error bounds
The effects of parameter on error bounds at different
subdivision levels of the control polygonand the limit curves
are shown in Figure 5 and Table 3. From Table 3 and Figure
5,we conclude that: In the case of the 3-point binary scheme,
the continuity is maximum over0<ߤ0<2and the error
bound is minimum over 0<ߤ0< 4. On each side of the
interval 0<ߤ0<2, the continuity decreases while error
bound increases on each side of the interval 0<ߤ0<4. In
the cases of the 3-point ternary and quaternary schemes, the
continuity is maximumover0<ߤ0<4 , while the error
bounds are minimum over 0<ߤ0<6 and 0 <ߤ0<
8,respectively. On each side of the interval 0<ߤ0<4, the
continuity decreases while the errorbound increases on each
side of the interval 0 <ߤ0< 6 and 0 <ߤ0< 8, respectively.
TABLE 3:ERROR BOUNDS FOR 3-POINT BINARY, TERNARY AND
QUATERNARY SCHEMES:
Scheme Parameter k = 1 k = 2 k = 3 k = 4
binary ߤ0 = 4 0.075000 0.037500 0.018750 0.009375
... ߤ0=െ1
3 0.110833 0.064653 0.037714 0.022000
... ߤ0=െ2
3 0.166667 0.111111 0.074074 0.049383
... Ɋ0=െ1 0.262500 0.196875 0.147656 0.110742
ternary ߤ0=6 0.033333 0.011111 0.003704 0.001235
... ߤ0=7 0.053333 0.023704 0.010535 0.004682
... ߤ0=െ3
2 0.075000 0.037500 0.018750 0.009375
... ߤ0=െ2 0.097222 0.054012 0.030007 0.016670
quaternary ߤ0=8 0.020833 0.005208 0.001302 0.000326
... ߤ0=9 0.025068 0.007050 0.001983 0.000558
... Ɋ0=െ1
2 0.028409 0.008878 0.002774 0.000867
... Ɋ0=െ5
4 0.032431 0.010641 0.003492 0.001146
Figure 5: Comparison: Error bounds between k-th level
control polygons and limit curvesgenerated by 3-point
schemes (13).
G.Conclusions and future research
We have shown that the 3-point approximating subdivision
schemes [1,2,3,4,6,11,12,14,15] can be derived from a-ary
3-point approximating subdivision scheme. In context of
binary and ternary subdivisions, we exploited a constructive
method for generating 3-point schemes. As observed, our
approach is more universal because it allows us to present
general formula for 3-point approximating schemes and
additionally it is applied to schemes of arbitrary arity.
Therefore, we conclude that 3-point schemes with higher
arity are better than lower arity schemes in the sense of
support, computational cost and error bounds. These
advantages motivates us to extend the proposed result to
surface subdivision.
5. Acknowledgement
Cop
y
ri
g
ht © 2012 SciRes.51
This work is supported bytheBeijing Municipal Natural
Science Foundation(4102027), theNational Natural Science
Foundation of China (60973101) and HEC, Pakistan.
REFERENCES
[1] M. Aslam, G. Mustafa, and A. Ghaffar, “(2n1)-point
ternary approximating and interpolatingsubdivision
schemes,” Journal of Applied Mathematics, Article ID
832630, 12 pages,2011.
[2] G. M. Chaikin, “An algorithm for high-speed curve
generation, Computer Graphics andImage
Processing,”vol. 3, 1974, pp. 346-349.
[3] S. Daniel and P. Shunmugaraj, “Three point stationary
and non-stationary subdivisionschemes,” 3rd
International Conference on Geometric Modeling &
Imaging,DOI:10.1109/GMAI.2008.13
[4] M. F. Hassan and N. A. Dodgson, “Ternary and three-
point univariate subdivision schemes,” in:A. Cohen, J. L.
Marrien, L. L. Schumaker (Eds.), Curve and Surface
Fitting: Sant-Malo2002, Nashboro Press, Brentwood, pp.
199-208, 2003.
[5] M. F. Hassan, I. P.Ivrissimitzis, N. A. Dodgson,and M.
A. Sabin, “An interpolating4-point ternary stationary
subdivision scheme,” Computer Aided Geometric
Design,vol. 19, pp.1-18, 2002.
[6] K. Hormann and M. A. Sabin, “A family of subdivision
schemes with cubic precision,” ComputerAided
Geometric Design, vol.25, 2008,pp. 41-52.
[7] F. Khan, G. Mustafa, “A new 4-point quaternary
approximating subdivision scheme,”Abstractand
Applied Analysis, doi:10.1155/2009/301967 (2009).
[8] J.-A. Lian, “On a-ary subdivision for curve design: III.
2mെ point and
(2m + 1)point
interpolatoryschemes,” Applications and Applied
Mathematics: An International Journal, vol. 4(2),2009,
pp. 434-444.
[9] J.-A. Lian, “On a-ary subdivision for curve design: I. 4-
point and 6-point interpolatoryschemes,” Applications
and Applied Mathematics: An International Journal, vol.
3(1), 2008, pp.18-29.
[10] J.-A. Lian, “On a-ary subdivision for curve design: II. 3-
point and 5-point interpolatoryschemes,” Applications
and Applied Mathematics: An International Journal, vol.
3(2), 2008, pp. 176-187.
[11] G. Mustafa, F. Khan and A. Ghaffar, The m-point
approximating subdivision scheme,Lobachevskii
Journal of Mathematics, vol. 30(2), 2009, pp. 138-145.
[12] G. Mustafa, A. Ghaffar and F. Khan, “The Odd-Point
Ternary Approximating Schemes,”American Journal of
Computational Mathematics, vol. 1(2), pp. 111-118,
2011. doi: 10.4236/ajcm.2011.12011
[13] G. Mustafa & M. S. Hashmi, Subdivision depth
computation for n-ary subdivisioncurves/surfaces, Vis
Comput, vol. 26, , 2010, pp. 841-851.
[14] S. S. Siddiqi and N. Ahmad, A new three point
approximating C2 subdivision scheme,Applied
Mathematics Letters, vol. 20, 2007, pp. 707-711.
[15] S. S. Siddiqi and Rehan, K, Modified form of binary
and ternary 3-point subdivisionscheme, Applied
Mathematics and Computation, vol. 216, 2010, pp. 970-
982.
52 Cop
y
ri
g
ht © 2012 SciRes.