# The Quaternary Interpolating Scheme for Geometric Design

Authors: Shahid S. Siddiqi; Muhammad Younis
Journal: ISRN Computer Graphics
 (2013)

---

## Abstract

A novel 4-point interpolating subdivision scheme is presented, which
generates the family ofC2 limiting curves and its limiting function has support on [−7/3,7/3]. It behaves better than classical 4-point binary and
ternary schemes with the same approximation order in many aspects
that it has smaller support size, higher smoothness, and is computationally
more efficient. The proposed nonstationary scheme can reproduce
the functions of linear spaces spanned by {1,sin(αx),cos(αx)}  for 0<α<π/3. Moreover, some examples are illustrated to show that
the proposed scheme can also reproduce asteroids, cardioids, and conic
sections as well.


---

## Body

## 1. Introduction

Subdivision schemes have become one of the most important, significant, and emerging modelling tools in computer applications, medical image processing, scientific visualization, reverse engineering, computer aided geometric designing, and so forth, because of their simple, elegant, and efficient ways to create smooth curves from initial control polygon by subdividing them according to some refining rules, recursively. These refining rules take the initial polygon to produce a sequence of finer polygons converging to a smooth limiting curve.In the field of nonstationary subdivision schemes, binary and ternary schemes are present in the literature [1–6]. But the quaternary schemes are not discussed as others. The aim of this paper is to introduce a quaternary nonstationary scheme which reproduces the linear functions spanned by {1,sin(αx),cos(αx)}. Moreover, the proposed scheme can also generate asteroids, cardioids, and in particular conic sections like circles, ellipses, and so forth. Some properties of the proposed scheme (like support size and symmetry of basic limit function, approximation order, convergence, and smoothness) have also been investigated. Besides the convergence and approximation order, the two important and interesting properties of basic limit function of a subdivision scheme are the support size and the smoothness. They are commonly manipulated with each other in the sense that a higher degree of smoothness generally requires a larger support, thus leading to a more global influence of each initial data value on the limit function. Raising the arity of the subdivision scheme provides a way to overcome this problem to some extent. The proposed scheme has smaller support and higher smoothness than the classical binary 4-point scheme, and all other schemes reproduce cubic polynomials by construction whether they are stationary or nonstationary [1–4, 6, 7].As interpolating subdivision schemes retain the points of stagek as the subset of the points of next stage k+1, thus the structure of a quaternary 4-point interpolating scheme in general form can be written as
(1)f4ik+1=fikf4i+1k+1=a0(k)fi-1k+a1(k)fik+a2(k)fi+1k+a3(k)fi+2kf4i+2k+1=b0(k)fi-1k+b1(k)fik+b2(k)fi+1k+b3(k)fi+2kf4i+3k+1=a3(k)fi-1k+a2(k)fik+a1(k)fi+1k+a0(k)fi+2k,
where the coefficients {aj(k)}j=0,1,2,3 and {bj(k)}j=0,1,2,3 are chosen to satisfy the relations ∑j=03‍aj(k)=1 and ∑j=03‍bj(k)=1, respectively, for a large value of k.This paper is organized as follows. In Section2 the basic notion and definitions of the quaternary subdivision scheme are considered. The construction of the proposed scheme has been shown in Section 3. In Section 4, the convergence and smoothness C2 of the scheme are being calculated using the theory of asymptotic equivalence. The basic limit function and its properties are being discussed in Section 5. The conclusion is drawn in Section 6.


## 2. Preliminaries

A quaternary subdivision scheme, to generate smooth curves or surfaces, is defined as the limit of refined control polygons or meshes, according to some refinement rules, recursively, in which the set of control pointsfk={fik∈R∣i∈Z} of polygon at kth level is mapped to a refined polygon to generate the new set of control points fk+1={fik+1∈R∣i∈Z} at the (k+1)st level by applying the following subdivision rule:
(2)fik+1={Sa(k)fk}i=∑j∈Z‍ai-4j(k)fjk∀i∈Z
with the sequence of finite sets of real coefficients {ai(k):k≥0}, constitute the so-called mask of the subdivision scheme. If the mask of a scheme is independent of k (namely, if a(k)=a for all k≥0), then it is called stationary Sa; otherwise it is called nonstationary Sa(k).The convergent subdivision schemeSa with the corresponding mask {ai,i∈Z} necessarily satisfies
(3)∑j∈Z‍a4j+l=1,l=0,1,2,3.It follows that the symbol of a convergent subdivision scheme satisfies the conditions(4)a(1)=4,a(e((2iπ/4)j))=0,j=1,2,3.For this, we introduce a symbol called the Laurent polynomial(5)a(z)=∑i∈Z‍aizi
of a mask {ai,i∈Z} with finite support. In view of Dyn [10], the sufficient and necessary conditions for a uniform convergent scheme are defined as follows.A quaternary subdivision schemeSa is uniformly convergent if and only if there is an integer L≥1, such that
(6)∥(14Sa1)L∥∞<1,
and subdivision Sa1 with symbol a1(z) is related to Sa with symbol a(z), where a1(z)=(4z3/(1+z+z2+z3))a(z) satisfying the property
(7)dfk=S1dfk-1,k=1,2,…,
where fk=Sakf0={fik:i∈Z} and dfk={(dfk)i=4k(fi+1k-fik):i∈Z}. The norm ∥Sa∥∞ of a subdivision scheme Sa with a mask ai,i∈Z, is defined by ∥Sa∥∞ and
(8)∥(14Sa)L∥∞=max{∑β‍|aγ+4Lβ[L]|:γ=0,1,…,4L-1},
where
(9)am[L](z)=∏j=0L-1‍am(z4j).The notation of convergence for quaternary subdivisionCm scheme, similar to that given by Dyn and Levin in [11] for a binary scheme, is given in the following.Definition 1.
A quaternary subdivision scheme{Sak} is said to be convergent if for every initial data f0∈l∞ there exists a limit function f∈Cm(R) such that
(10)limk→∞supi∈Z|fik-f(4-ki)|=0,
and f is not identically zero for some initial data f0.Definition 2.
Two quaternary subdivision schemes{Sa(k)} and {Sb(k)} are said to be asymptotically equivalent if
(11)∑k=1∞‍∥Sa(k)-Sb(k)∥∞<∞,
where
(12)∥Sa(k)∥∞=max{∑j=Z‍|a4i(k)|,∑i∈Z‍|a4i+1(k)|,∑i∈Z‍|a4i+2(k)|,∑i∈Z‍|a4i+3(k)|}.Theorem 3.
Let{Sak} and {Sa} be quaternary nonstationary and stationary subdivision schemes, respectively, which are said to be asymptotically equivalent if they have finite masks of the same support. If stationary scheme {Sa} is Cm and
(13)∑k=0∞‍4mk∥Sa(k)-Sa∥∞<∞,
then nonstationary scheme {Sak} is also Cm.


## 3. The Nonstationary Subdivision Scheme

In this paper, an interpolating 4-point nonstationary scheme is presented which is associated with Lagrange-like cubic trigonometric interpolants. For this, consider a spaceτ:=span{1,sin(αx),cos(αx)} for some α such that 0<α<π, for the data set, D={(x-1,f(x-1)),(x0,f(x0)),(x1,f(x1)),(x2,f(x2))}, and also consider the function,
(14)L(x)=∑j=-12‍f(xj)Lj(x),
where
(15)Lj(x)=∏k=-1,k≠j2‍sin((α/4)(x-xk))sin((α/4)(xj-xk)),
is a unique function in τ which interpolates the data set with having minimum amplitude among other interpolants from τ [12], where the function L(x) is called the trigonometric Lagrange-like interpolant of the previous data. Since the function Lj(x) is defined for xj=j,j=-1,0,1,2, where Lj(x) is represented by LjDm(x), m=1,2,3 for the following discussion.(i)
IfD1={xj=j:j=-1,0,1,2andx′=1/4}, then
(16)L-1D1(x′)=-sin(α/16)sin(3α/16)sin(7α/16)sin(α/4)sin(2α/4)sin(3α/4),L0D1(x′)=sin(3α/16)sin(5α/16)sin(7α/16)sin2(α/4)sin(2α/4),L1D1(x′)=sin(α/16)sin(5α/16)sin(7α/16)sin2(α/4)sin(2α/4),L2D1(x′)=-sin(α/16)sin(3α/16)sin(5α/16)sin(α/4)sin(2α/4)sin(3α/4).(ii)
IfD2={xj=j:j=-1,0,1,2andx′′=1/2}, then
(17)L-1D2(x′′)=L2D2(x′′)=-sin2(α/8)sin(3α/8)sin(α/4)sin(2α/4)sin(3α/4),L0D2(x′′)=L1D2(x′′)=sin(α/8)sin2(3α/8)sin2(α/4)sin(2α/4),
and similarly, it can be obtained for the following.(iii)
IfD3={xj=j:j=-1,0,1,2andx′′′=3/4}, then
(18)L-1D1(x′)=L2D3(x′′′),L0D1(x′)=L1D3(x′′′),L1D1(x′)=L0D3(x′′′),L2D1(x′)=L-1D3(x′′′).After that, adjust the previous values to the masks{aj(k)}j=0,1,2,3 of the subdivision scheme (1) in the following manner:
(19)a0(k)=sin(α/2k+4)sin(3α/2k+4)sin(7α/2k+4)sin(α/2k+2)sin(2α/2k+2)sin(3α/2k+2)=L-1D1(x′)=L2D3(x′′′)a1(k)=sin(3α/2k+4)sin(5α/2k+4)sin(7α/2k+4)sin2(α/2k+2)sin(2α/2k+2)=L0D1(x′)=L1D3(x′′′)a2(k)=sin(α/2k+4)sin(5α/2k+4)sin(7α/2k+4)sin2(α/2k+2)sin(2α/2k+2)=L1D1(x′)=L0D3(x′′′)a3(k)=sin(α/2k+4)sin(3α/2k+4)sin(5α/2k+4)sin(α/2k+2)sin(2α/2k+2)sin(3α/2k+2)=L2D1(x′)=L-1D3(x′′′),
and also we have
(20)b0(k)=b3(k)=sin2(α/2k+3)sin(3α/2k+3)sin(α/2k+2)sin(2α/2k+2)sin(3α/2k+2),b1(k)=b2(k)=sin(α/2k+3)sin2(3α/2k+3)sin2(α/2k+2)sin(2α/2k+2).Thus, an interpolating 4-point nonstationary subdivision rule to refine the control polygon is defined in (21), where the mask of proposed scheme satisfies the affine properties, presented by the set of (19) and (20). So, we have
(21)f4ik+1=fikf4i+1k+1=-a0(k)fi-1k+a1(k)fik+a2(k)fi+1k-a3(k)fi+2kf4i+1k+1=-b0(k)fi-1k+b1(k)fik+b2(k)fi+1k-b3(k)fi+2kf4i+2k+1=-a3(k)fi-ik+a2(k)fik+a1(k)fi+1k-a0(k)fi+2k.It may be noted that the points((4i+1)/4k+1,f4i+1k+1), ((4i+2)/4k+1,f4i+1k+1), and ((4i+3)/4k+1,f4i+1k+1) lie on the Lagrange-like interpolant of the set of points {((i-1)/4k,fi-1k),(i/4k,fik),((i+1)/4k,fi+1k), and ((i+2)/4k,fi+2k)}. Moreover, the mask of scheme (21) is bounded by the following coefficients:
(22)a0k⟶7128,a1k⟶105128,a2k⟶35128,a3k⟶5128,b0k=b3k⟶116,b1k=b2k⟶916.The proof of the previous boundedness can be followed from Lemma4.


## 4. Convergence and Smoothness

The theory of asymptotic equivalence is used to investigate the convergence and smoothness of the scheme following [11]. For this, some estimations of ai(k),i=0,1,2,3 and bi(k),i=0,1,2,3 used are given in the following lemmas. To prove the lemmas, the following three inequalities are used:
(23)sinasinb≥abfor0<a<b<π2,θcscθ≤tcsctfor0<θ<t<π2,cosx≤sinxxfor0<x<π2.Lemma 4.
Fork≥0 and 0<α<π/2, one has
(24)(i)7128≤a0(k)≤71281cos3(3α/2k+1),(ii)105128≤a1(k)≤1051281cos3(α/2k+1),(iii)35128≤a2(k)≤351281cos3(α/2k+1),(iv)5128≤a3(k)≤51281cos3(3α/2k+1),(v)116≤b0(k)≤1161cos3(α/2k+1),(vi)916≤b1(k)≤9161cos3(3α/2k+1).Proof.
To prove the inequality (i)(25)a0(k)=sin(α/2k+4)sin(3α/2k+4)sin(7α/2k+4)sin(α/2k+2)sin(2α/2k+2)sin(3α/2k+2)≥(α/2k+4)(3α/23k+4)(7α/2k+4)(α/23k+2)(2α/2k+2)(3α/2k+2)=7128,a0(k)≤21α323k+12csc(α2k+2)csc(2α2k+2)csc(3α2k+2)≤21α323k+1236csc3(3α2k+1)≤21α323k+12361(3α/2k+1)3cos3(3α/2k+1)(26)≤71281cos3(3α/2k+1).
The proof of (ii), (iii), (iv), (v), and (vi) can be obtained similarly.Lemma 5.
For some constantsC0,C1,C2,C3,C4, and C5 independent of k, one has the following:
(27)(i)|a0(k)-7128|≤C014k,(ii)|a1(k)-105128|≤C114k,(iii)|a2(k)-35128|≤C214k,(iv)|a3(k)-5128|≤C314k,(v)|b0(k)-116|≤C414k,(vi)|b1(k)-916|≤C514k.Proof.
Inequality (i) can be proved using Lemma4. So
(28)(i)|a0(k)-7128|≤7128(1-cos3(3α/(2k+1))cos3α)≤7128(3sin2(3α/(2k+1))2cos3α)≤189α21024cos3α14k.
The proof of (ii), (iii), (iv), (v), and (vi) can be obtained similarly.Lemma 6.
The Laurent polynomiala(k)(z) of the scheme {Sa(k)} at the kth level can be written as a(k)(z)=((1+z+z2+z3)/4)c(k)(z), where
(29)c(k)(z)=4{-a3(k)z4+(a3(k)-b0(k))z3+(b0(k)-a0(k))z2+a0(k)z+(a2(k)-a3(k))+(b1(k)-b0(k)-a2(k)+a3(k))z-1+(a1(k)-a0(k)-b1(k)+b0(k))z-2+(a2(k)-a3(k))z-3+a0(k)z-4+(b0(k)-a0(k))z-5+(a3(k)-b0(k))z-6-a3(k)z-7}.Proof.
Since(30)ak(k)(z)=-a3(k)z7-b3(k)z6-a0(k)z5+a2(k)z3+b2(k)z2+a1(k)z+1+a1(k)z-1+b1(k)z-2+a2(k)z-3-a0(k)z-5-b0(k)z-6-a3(k)z-7,
therefore using-a0(k)+a1(k)+a2(k)-a3(k)=1 and -b0(k)+b1(k)=1/2 following result can be established a(k)(z)=((1+z+z2+z3)/4)b(k)(z).Lemma 7.
The Laurent polynomiala(z) of the scheme {Sa} can be written as a(z)=((1+z+z2+z3)/4)c(z), where
(31)c(z)=132{-5z4-3z3+z2+7z+30+34z-1+34z-2+30z-3+7z-4+z-5-3z-6-5z-7},
and the subdivision scheme {Sc} corresponding to the symbol c(z) is C1.Proof.
The mask defined by the scheme{Sc} converges and has the smoothness C1 (it can be proved using Laurent polynomial method). If {Sc} is C1, then {Sa} with the mask
(32)1128[-5,8,-7,0,35,72,105,128,105,72,35,0,-7,8,-5]
is C2.Theorem 8.
The scheme defined by (21) converges and has smoothness C2.Proof.
To prove the proposed scheme to beC2, it is sufficient to show that the scheme corresponding to ck(z) is C1 (Theorem (8) given by Dyn and Levin [13]). Since {Sc} is C1 by Lemma 7, then following Theorem 3, it has been shown that the schemes {Sc(k)} and {Sc} are asymptotically equivalent. So we have to show that
(33)∑k=0∞‍4k∥Sc(k)-Sc∥∞<∞,
where
(34)∥Sc(k)-Sc∥∞=max{∑j=Z∞‍|ci+4j(k)-ci+4j|:i=0,1,2,3}.
From Lemmas6 and 7, it can be written as
(35)∑j∈Z∞‍|c4j(k)-c4j|=|4a3k-532|+|4a2k-4a3k-3032|+|4a0k-732|=4|a0k-7128|+4|a2k-35128|+8|a3k-5128|=∑j∈Z∞‍|c4j+3k-c4j+3|.
Similarly, one can obtain(36)∑j∈Z∞‍|c4j+1(k)-c4j+1|=4|a0k-7128|+4|a2k-35128|+8|a3k-5128|+12|b0k-116|+4|b1k-916|,∑j∈Z∞‍|c4j+2(k)-c4j+2|=8|a0k-7128|+4|a1k-105128|+4|a3k-5128|+12|b0k-116|+4|b1k-916|.
From Lemma5, we have ∑k=0∞‍4k|a0(k)-7/128|<∞, ∑k=0∞‍4k|a1(k)-105/128|<∞,∑k=0∞‍4k|a2(k)-35/128|<∞, ∑k=0∞‍4k|a3(k)-5/128|<∞,∑k=0∞‍4k|b0(k)-1/16|<∞, and ∑k=0∞‍4k|b1(k)-9/16|<∞. So, it can be written as
(37)∑k=0∞‍4k∥Sc(k)-Sc∥∞<∞.
Thus, the scheme corresponding to symbolc(k)(z) is C1 and hence the scheme (21) is C2.Figure1 shows the reproduction of the unit circle and ellipse by the proposed scheme (21), taking regular hexagon as control points for circle.The reproduction of the unit circle and ellipse by the proposed scheme.
(a)
(b)In Figure2, twelve points have been taken as control points on the parametric curves of asteroid: x(t)=3cost+cos3t,y(t)=3sint-sin3t and cardioid: x(t)=(1-cost)sint,y(t)=(1-cost)cost to reconstruct the asteroid and cardioid, respectively, by the proposed scheme.The reconstruction of asteroid and cardioid by the proposed scheme.
(a)
(b)Figure3 shows the behavior of basic limit function for different values of α.Basic limit function of proposed scheme for different values ofα.
(a)
(b)


## 5. Properties of the Scheme

In this section some properties (approximation order, reproduction property, support size, and symmetry of basic limit function) are being discussed. The results show that the proposed scheme with the same approximation order has the higher smoothness and smaller support than the existing 4-point interpolating subdivision schemes (see also Table1).Table 1
Comparison of the 4-point interpolating subdivision schemes.
Scheme
Type
Continuity
Approximation order
Support
Binary [8]
Stationary
C
1
4
[−3, 3]
Ternary [9]
Stationary
C
2
3
[−2.5, 2.5]
Proposed (32)
Stationary
C
2
4
[−2.3, 2.3]
Binary [1]
Nonstationary
C
1
4
[−3, 3]
Binary [2]
Nonstationary
C
1
4
[−3, 3]
Ternary [3]
Nonstationary
C
2
3
[−2.5, 2.5]
Ternary [4]
Nonstationary
C
2
3
[−2.5, 2.5]
Proposed (21)
Nonstationary
C
2
4
[−2.3, 2.3]Another advantage (see also [14]) of the scheme is the computational cost. In one subdivision step, for a sequence of n points the proposed scheme requires 12n multiplications and 9n additions. On the other hand, computing the same number of 4n refined points with the binary scheme requires two subdivision steps with a total cost of 18n multiplications and 9n additions, so the quaternary scheme is more efficient.The basic limit function of the scheme is symmetric aboutY-axis for the data
(38)fi0={1,i=0,0,i≠0.Theorem 9 (see [3]).
The basic limit functionF is symmetric about the Y-axis.Proof.
LetF denote the basic limit function and define Dn:={i/4n∣i∈Z} such that restriction of F to Dn satisfies F(i/4n)=fin for all i∈Z. The symmetry of basic function is proved using induction on n.
It can be observed thatF(i)=F(-i) for all i∈Z; thus F(i/4n)=F(-i/4n) for all i∈Z and n=0. Assume that F(i/4n)=F(-i/4n) for all i∈Z and then fin=f-in for all i∈Z. It may be observed that
(39)F(4i4n+1)=f4in+1=f-4in+1=F(-4i4n+1),F(4i+14n+1)=f4i+1n+1=-a0nfi-1n+a1nfin+a2nfi+1n-a3nfi+2n=-a3nf-i-2n+a2nf-i-1n+a1nf-in-a0nf-i+1n=f-4i-1n+1=F(-4i+14n+1).
Similarly(40)F(4i+24n+1)=f4i+2n+1=f-4i-2n+1=F(-4i+24n+1),F(4i+34n+1)=f4i+3n+1=f-4i-3n+1=F(-4i+34n+1).
Hence,F(i/4n)=F(-i/4n) for all i∈Z and n=Z+; thus from the continuity of F, F(x)=F(-x) holds for all x∈R, which completes the required result.In the following the support of basic limit function of the proposed scheme has been calculated generated by the control pointfi0Theorem 10.
The basic limit function F defined by the scheme vanishes outside[-7/3,7/3].Proof.
Definetn recursively by taking tn+1=tn+1/4n+1 with t0=0. It can be observed that tn∈Dn1 but tn∉Dn-11. We claim that restriction of F to Dn vanishes outside [-tn,tn]. Since F is symmetric, it is enough to prove that F vanishes outside [0,tn]. Thus, after kth subdivision step, the furthest nonzero vertex on the left/right will be at (7/4)∑j=0k-1‍(1/4j). So, it can be concluded that the left or right influence of the original nonzero vertex will propagate along limn→∞tn=∑j=0∞‍(7/4)(1/4)j=(7/4)(1/(1-(1/4)))=7/3. It can be concluded that [-tn,tn] is contained in [-7/3,7/3] for all n and limn→∞[-tn,tn]=[-7/3,7/3], which is the required result.Theorem 1111(see [15]).
A convergent subdivision scheme that reproduces polynomialπn has an approximation order n+1.So in the light of the previous theorem, the proposed scheme has approximation order4 because the construction of mask is formulated through the cubic trigonometric polynomials.The polynomial reproduction property has its own importance, as the reproduction property of the polynomials up to certain degreed implies that the scheme has d+1 approximation order. For this, polynomial reproduction can be made from initial data which has been sampled from some polynomial functions. So, in view of the previous theorem, scheme (32) has approximation order 4.


## 6. Conclusion

A 4-point novel quaternary interpolating nonstationary subdivision scheme has been developed which generates the family ofC2 limiting curves and its limiting function has support on [-7/3,7/3]. The nonstationary scheme is associated with trigonometric polynomials which reproduces the functions of linear spaces spanned by {1,sin(αx),cos(αx)} for 0<α<π/3. The comparison shows that, with existing stationary and nonstationary interpolating schemes, the proposed scheme is better. Moreover, it also can reconstruct or reproduce the conic sections, asteroids, and cardioids.



---

*Source: 434213-2013-04-17.xml*