American Journal of Computational Mathematics, 2013, 3, 217-221
http://dx.doi.org/10.4236/ajcm.2013.33031 Published Online September 2013 (http://www.scirp.org/journal/ajcm)
A Family of 4-Point n-Ary Interpolating Scheme
Reproducing Conics
Mehwish Bari, Ghulam Mustafa
Department of Mathematics, The Islamia University of Bahawalpur, Bahawalpur, Pakistan
Email: ghulam.mustafa@iub.edu.pk, mehwishbari@yahoo.com
Received April 16, 2013; revised June 5, 2013; accepted July 5, 2013
Copyright © 2013 Mehwish Bari, Ghulam Mustafa. This is an open access article distributed under the Creative Commons Attribu-
tion License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly
cited.
ABSTRACT
The n-ary subdivision schemes contrast favorably with their binary analogues because they are capable to produce limit
functions with the same (or higher) smoothness but smaller support. We present an algorithm to generate the 4-point
n-ary non-stationary scheme for trigonometric, hyperbolic and polynomial case with the parameter for describing curves.
The performance, analysis and comparison of the 4-point ternary scheme are also presented.
Keywords: Interpolation; Non-Stationary; Univariate Ternary Refinement; Continuity; Conic Section
1. Introduction
Subdivision is a method for making smooth curves/sur-
faces, which first emerged an addition of splines to arbi-
trary topological control nets. Effectiveness of subdivi-
sion algorithms, their flexibility and ease make them ap-
propriate for many relative computer graphics applica-
tions. The schemes generating curves are considered to
be the basic tools for the design of schemes generating
surfaces.
A general form of univariate n-ary subdivision scheme
S which maps a control polygon
kk
ii
ff
to a re-
fined polygon
11kk
ii
ff

is defined by
1,0,1,2,,
kk
ni snj sij
j
fafS


1,n
where the set
i
aai of coefficients is called
mask of the subdivision scheme. The set of coefficients
:
kk
i
aai
kk
a
d etermines the subdivision ru le at level
and is termed as the mask at -th level. If the mask
is independent of , namely if , the
subdivision scheme is called stationary otherwise it is
called non-stationary. Sometimes, in computer graphics
and geometric modeling, it is required to have schemes
to construct circular parts or parts of conics. It seems that
(linear) stationary schemes cannot generate conics and
non-stationary schemes have such a capability to gener-
ate trigonometric polynomials, trigonometric splines and,
in particular, circles, ellipses and so on. Such schemes
k
k,
k
aak
are useful in computer graphics and geometric modeling.
Successful efforts have been made to establish approxi-
mating and interpolating non-stationary schemes which
can provide smooth curves and reproduce circle or some
trigonometric curves.
The theoretical bases regarding non-stationary schemes
are derived from the analysis of stationary schemes. Jena
et al. [1] worked on 4-point binary non-stationary subdi-
vision scheme for curve interpolation. Yoon [2] pre-
sented the analysis of binary non-stationary interpolating
scheme based on exponential polynomials. Beccari et al.
[3] worked on 4-point binary non-stationary uniform ten-
sion controlled interpolating scheme reproducing conics.
Daniel and Shunmugaraj [4] presented 4-point ternary
non-stationary interpolating subdivision scheme. In this
paper, we present an algorithm to construct 4-point n-ary
scheme. For simplicity, we have discussed and analyzed
4-point ternary scheme.
This paper is organized as follows. Section 2 presents
the construction of 4-point n-ary non-stationary interpo-
lating subdivision schemes. As an example, 4-point ter-
nary scheme is presented in this section. Section 3 pro-
vides the smoothness of proposed schemes. In the last
section conclusion and visual performance of proposed
schemes are presented.
2. Construction of 4-Point n-Ary Scheme
Here we suggest the following algorithm to construct the
non-stationary n-ary 4-point
2,3,4, ,n interpo-
C
opyright © 2013 SciRes. AJCM
M. BARI, G. MUSTAFA
218
lating schemes for trigonometric, hyperbolic and poly-
nomial cases.
Choose interpolating function

01 23
cossin ,
f
xaaxaxa x 

01 23
cosh sinh or
,
f
xaaxa xa 
x
or
23
01 23
.
f
xaaxaxax 
Then define the points

k
i
pi at level k and
get system of linear equations by interpolating.
The data k
ih
p corresponding to the abscissas
,1,0,1,
k
ht
xh
n
2.
Solve the system of linear equations by any well
known method to get the values of unknowns.
Evaluate the interpolating function
f
x at the grid
points
1
1:2,3,,.
k
rt
rn
n
Define the new points 1.
kk
ni i
pp
Define the new points

11
1,1,2,3,,
k
ni jk
rt
pf jrr
n




,n
as a lin-
ear combination of four consecutive points 1
k
i
p
, ,
and
k
i
p
1
k
i
p2.
k
i
p
Ternary 4-Point Interpolating Scheme
Given a set of control points at level , using
above algorithm, we define a unified ternary 4-point in-
terpolating scheme that makes a new set of control points
by the rule:
k
Pk
1k
p
1
3
1
3111 23142
1
324 132 112
,
,
,
kk
ii
kkkkkkkkk
iiiii
kkkkkkkkk
iiii
pp
ppppp
ppppp


 
 


where
11
24 1,
kk
k5

 
3
21 1
41(161)
kk
kk
5
,


 
43
3111
4882 1,
kk
kkk5
 


41
41
kk
k5
,

 
with

2
2
511
641 21,
kkk
 

 
where the parameter 1k
can easily be updated at each
subdivision step through following equation
10
1,0,1,2,, 1,
2k
kk

.
 (2.2)
Therefore, given parameter ,
k
the subdivision rules
are achieved by first computing 1k
using Equation
(2. 2) an d th en by substituting 1k
into (2.1). As a result,
depending on the choice of the parameter, we get differ-
ent schemes. For

11
1cos
h 3
kk
t

i
3 ,cost
k and 1
in (2.1), we can generate following schemes exact for tri-
gonometric (2.3), hyperbolic (2.4) and polynomial (2.5)
respectively.
1
3
1
3111231 42
1
324 132 112
,
,
,
kk
ii
kkkkkkkkk
iiiii
kkkkkkkkk
iiii
pp
ppppp
ppppp



 


(2.3)
where
i
(2.1)

1
12sin33sin 23,
kkk
tt
k
 


11
22sin2 3sin36sin233sin3,
kkkkk
tt tt
k




11
33sin 23sin 232sin36sin3,
kkkkk
tttt
k


 

1
4sin 33sin 3,
kkk
tt
k
 


6sin3cos 31
kkk
tt
.
1
3
1
3111 231 42
1
324 132 112
,
,
,
kk
ii
kkkkkkkkk
iiiii
kkkkkkkkk
iiii
pp
ppppp
ppppp


 
 


kk
i
(2.4)
where 11
,
22
,
kk
33
,
kk
44
,
kk
after
replacing sin and cos functions by sinh and cosh func-
tions in 12
,,
k34
,.
kkk

1
3
1
3111 2
1
3211 2
,
560304
,
81818181
430605
,
81 8181 81
kk
ii
kkkk
iiii
kkkk
iiii
pp
ppppp
pppp
 
 
 

k
i
k
i
p
(2.5)
Remark 2.1. The scheme (2.3) and (2.4) can be consid-
ered as a non-stationary counterpart of the DD stationary
scheme [5] i.e. scheme (2.5) because, the masks of the
schemes (2.3) and (2.4) converge to the mask of scheme
(2.5):
Copyright © 2013 SciRes. AJCM
M. BARI, G. MUSTAFA 219
1122 33
44
560
,,
81 8181
4,.s
81 a
kkkk kk
kk k


 
 
30
,
3. Smoothness Analysis
The subdivision scheme given in the previous subsection,
the coefficients
1,2 ,3,4
k
ii
in (2.1) may vary from one
refinement level to another. Hence the scheme is non-
stationary and its smoothness properties can be derived
by asymptotical equivalence [6] with the corresponding
stationary scheme. Two subdivision schemes and
are said asymptotically equivalent if k
a
S
a
S
.
ka
ka
SS

In particular, our analysis is based
on the generalization of Theorem 8 in [6] to ternary sub-
division.
Since our schemes (2.3) and (2.4) are non-stationary
then we can use the theory of asymptotic equivalence and
generating function formalism [7] to investigate the
smoothness of the schemes. First, we need some esti-
mates of k
i
and which are specified
in subsequent lemmas. ,1,2,3,4,
k
ii
Lemma 3.1.
The mask of scheme (2.3) satisfies following inequali-
ties for sufficiently large .
k
1) 1
12
,
33
k

2) 2
41,
3
k
 
3) 3
104 ,
27 3
k

4) 4
11
.
63
k

Proof. We make use the inequalities sin
sin
aa
bb
for
02
ab
 , csc csctt
for 02
t
 and
sin
cos
x
x
x
(or 1
csc xcos
x
x
) for 02
x
 to
prove the above inequa lities:
Since
 


 

11
12
1
22
2sin36sin 3cos3
12sin3sin2 3
sin 3sin 3cos3.
6sin3sin2 32sin3sin2 3
kkk
k
kk
kk
kkkk
ttt
tt
tt
tt tt



k
t
Then for
k
 
11
12
13cos 313cos 31
63
6sin23
kk
k
k
tt
t



and also for , we get
k





1
12
21
2
2sin36sin3cos3
12sin3sin2 3
22 6sin232.
3
12sin2 3
kk
k
kk
k
k
ttt
tt
t
t





k
This proves 1). The pro o fs of 2) , 3) an d 4) are sim i l ar.
Lemma 3.2.
The coefficients in the scheme (2.4) satisfy following
inequalities when subdivision level .
k
1) 1
10,
3
k

2) 2
77
,
66
k

3) 3
44
,
33
k

4) 4
10.
6
k

Proof. We make use of following inequality of [8]
2
11cos
cos,,.
cosh2222
xx
x
x

 
 
 
 
This claim holds true if the function
f
x is non-
negative on
0, 2.
Some other inequalities for 02
x
 are
1
2
sinhsinh,sinh 0,
33
kk
xx
x
 
 
 
11
,0
coshsinh1 cosh
x
xx x
.
Since

 


 

1
1
2sinh33sinh 23
6sinh3cosh31
2sinh3.
6sinh3cosh31
kk
k
kk
k
kk
tt
tt
t
tt

Then for
k








1
2
1cos 3
1
33cosh313 1cos3
1cos 31,
3
32sin23
k
k
kk
k
k
t
tt
t
t
 

 
Copyright © 2013 SciRes. AJCM
M. BARI, G. MUSTAFA
220
and similarly for
k
 
 


 

1
1
2sinh33sinh23
6sinh3cosh31
3sinh 30.
6sinh 3cosh 31
kk
k
kk
k
kk
tt
tt
t
tt

This proves 1). The pro o fs of 2) , 3) an d 4) are sim i l ar.
The following two Lemmas are the consequence of
previous Lemm as.
Lemma 3.3.
1) 1559
,
81 81
k




2) 260 21,
81 81
k

3) 330 78,
81 81
k

4) 4431
.
81 81
k




Proof. Since 15
81
k
 as and by 1) of
k
Lemma 3.1, we have 1). Similarly, we get 2), 3) and 4).
Lemma 3.4.
1) 155
,
81 81
k




2) 260 23,
81 54
k

3) 330 78,
81 81
k

4) 444
.
81 81
k




Proof. Since 15
81
k
 as and by 1) of
k
Lemma 3.2, we have 1). Similarly, we get 2), 3) and 4).
Lemma 3.5.
The Laurent polynomial
kz
of the level of
the scheme
th
k
k
S
defined by (2.1) can be written as
 
2
1
3
kk
zz
zaz



2
1
where

 


543
414 1 34
123434
123
1144
33 33
33
33 3.
kkkkkkk
kkkk kk
kkk k
azzz zz
z
zzz

 





Proof. By (2.1), we have

5421
413 22
245
314
1
.
k kkkkk
kkk
zzzzzz
zzz
 


 

It can be easily verified that
 
2
1.
3
kk
zz
za




z
Lemma 3.6.
The stationary scheme
a
S defined by (2.5) associ-
ated with the symbol

542 1
245
145306081 60
81
30 5 4
azzzzzz
zzz
1



is
1.C
Proof. To prove that
a
S is consider
1,C



2
2
32123
3
1
14 3 617634.
27
az
bz zz
zzzzzz



Since
3313
max ,,
25 99
max, ,1
27 27 27
bjj
jj j
Sbb






 

2j
b
then by [[7], corollary 4.11] the scheme
a
S is
1.C
Lemma 3.7.
The scheme k
S
defined by (2.1) is
1.C
Proof. Since
a
S is by Lemma 3.6, in view of
[[6], Theorem 8(a)], it is sufficient to show that
1
C
03k
ka
k
SS

where
333131 3232
1434
14 1234
max ,,
54 26
max 3333,
27 2727
12
2333333 .
27 27
ka
kk k
jjj jjj
jj j
kkkk
kk kkkk
SS
aa a



 
 
9
 


 
 

Note that
1234
1234
29
333327
56030.
81818181
kkkk
kkkk



4

Since 1
0
5
3,
81
kk
k




Copyright © 2013 SciRes. AJCM
M. BARI, G. MUSTAFA
Copyright © 2013 SciRes. AJCM
221
5. Acknowledgements
2
0
60
3,
81
kk
k




3
0
30
381
kk
k




and This work is supported by the Indigenous Ph.D Schol-
arship Scheme of Higher Education Commission (HEC)
Pakistan.
1
0
4
3
81
kk
k




,
then by Lemma 3.3, it follows
that REFERENCES
11234
0
29
3
81
kkkkk
k


.
[1] M. K. Jena, P. Shunmugaraj and P. C. Das, “A Non-Sta-
tionary Subdivision Scheme for Curve Interpolation,”
ANZIAM Journal, Vol. 44, No. E, 2003, pp. 216-235.
By Lemma 3.3, we can also show that
1
0
5
33 ,
27
kk
k

4
0
4
33 ,
27
kk
k

[2] J. Yoon, “Analysis of Non-Stationary Interpolatory Sub-
division Schemes Based on Exponential Polynomials,”
Geometric Modeling and Processing, Vol. 4077, 2006, pp.
563-570.
34
0
26
33 327
kk k
k


and [3] C. Beccari, G. Casciola and L. Romani, “A Non-Station-
ary Uniform Tension Controlled Interpolating 4-Point
Scheme Reproducing Conics,” Computer Aided Geomet-
ric Design, Vol. 24, No. 1, 2007, pp. 1-9.
doi:10.1016/j.cagd.2006.10.003
14
0
2
36 6.
27
kkk
k


Hence 03k
ka
kSS
. [4] S. Daniel and P. Shunmugaraj, “Some Interpolating Non-
Stationary Subdivision Schemes,” International Sympo-
sium on Computer Science and Society, Kota Kinabalu,
16-17 July 2011, pp. 400-403.
doi:10.1109/ISCCS.2011.110
4. Conclusions
To the aim of reproducing conic sections, we introduce
an algorithm for generation of 4-point n-ary interpolating
scheme. In particular, we define 4-point interpolating
scheme that unifies three different curves schemes which
are capable of representing trigonometric, hyperbolic and
polynomial functions.
[5] G. Deslauriers and S. Dubuc, “Symmetric Iterative Inter-
polation Processes,” Constructive Approximation, Vol. 5,
No. 1, 1989, pp. 49-68. doi:10.1007/BF01889598
[6] N. Dyn and D. Levin, “Analysis of Asymptotically Equi-
valent Binary Subdivision Schemes,” Journal of Mathe-
matical Analysis and Applications, Vol. 193, No. 2, 1995,
pp. 594-621. doi:10.1006/jmaa.1995.1256
The resulting ternary algorithm allows u s to efficiently
define limit curves that combine all the ingredients of
locality, smoothness, user-independence, local ten-
sion control and reproduction of conics, see Figure 1.
1
C[7] N. Dyn and D. Levin, “Subdivision Schemes in Geomet-
ric Modelling,” Acta Numerica, Vol. 11, 2002, pp. 73-144.
doi:10.1017/S0962492902000028
[8] R. Klen, M. Lehtonen and M. Vuorinen, “On Jordan Type
Inequalities for Hyperbolic Functions,” Journal of Ine-
qualities and Applications, Vol. 2010, 2010, Article ID:
362548.
(a) (b) (c) (d)
Figure 1. Dotted lines indicate the initial closed and open
polygons. Solid continuous curves are generated by pro-
posed ternary interpolating scheme for trigonometric case.