1. Introduction
Until a few years ago all the work in the area of univariate subdivision was limited to consider just binary (Chaikin [1]; Dyn et al. [2,3]; Siddiqi and Younis [4]; Beccari et al. [5]) and ternary (Hassan and Dodgson [6]; Hassan et al. [7]; Ko et al. [8]; Mustafa et al. [9]) scenarios. In recent time, some proposals of quaternary subdivision schemes have introduced new interest in the era of subdivision, showing the possibility of treating refinement schemes with arity other than two or three.
Since subdivision schemes propose efficient iterative algorithms to produce the smooth curves and surfaces from a discrete set of control points by subdividing them according to some refining rules, recursively. These refining rules are very helpful and useful for the creation of smooth curves and surfaces in computational geometry and geometric designing due to their wide range of applications in many areas like engineering, medical science and image processing etc.
In this article an algorithm has been introduced to produce the quaternary 
point (for any integer
) approximating subdivision schemes. This algorithm has been developed using the Cox-de Boor recursion formula, in the form of uniform B-spline blending functions to produce piecewise polynomials of order 
over the interval 
(for detail, see Section 2).
The quaternary subdivision scheme can be defined in terms of a mask consisting of a finite set of non-zero coefficients 
as follows
The formal definitions and the notion for the convergence analysis of the quaternary subdivision scheme are as follows:
The quaternary convergent subdivision scheme 
with the corresponding mask 
necessarily satisfies
It follows that the symbol of a convergent subdivision scheme satisfies the conditions 
and
for
.
Introducing a symbol called the Laurent polynomial
of a mask 
with finite support. In view of Dyn [3], the sufficient and necessary conditions for a uniform convergent scheme are defined as follows.
A subdivision scheme 
is uniform convergent if and only if there is an integer
, such that
subdivision 
with symbol 
is related to S with symbol
, where 
and satisfying the property
where 
and
The norm 
of a subdivision scheme 
with a mask 
is defined by
and
where
where
and
The paper is organized as follows, in Section 2 the algorithm to construct 
-point (for any integer
) quaternary schemes has been introduced. Three examples are considered to produce the masks of 2-point (corner cutting), 3-point and 4-point schemes in the same section. In Section 3, the polynomial reproduction property has been discussed. The conclusion is drawn in Section 4.
2. Construction of the Algorithm
In this section, an algorithm has been constructed to produce the quaternary 
-point approximating subdivision schemes using the uniform B-spline basis functions and the Cox-de Boor recursion relation. The Cox-de Boor recursion relation, in view of Buss [10], can be defined as follows:
The recursion relation is the generalization to B-spline of degree 
(or of order
, i.e.,
). For this, consider 
to be a set of 
non-decreasing real numbers in such a way that
. The values
’s, not necessarily uniformly spaced, are called knots of non-uniform spline and the set 
is called knot vector. The uniform B-splines are just the special case of non-uniform B-splines in which the knots are equally spaced such that 
is a constant for 
(i.e.,
) . Note that the blending functions 
of order 
depend only on the knot positions and are defined by induction on 
as follows.
First, for 
let
Second for
. Setting
, 
is defined by the Cox-de Boor formula as,
(1)
The form of above recursive formulas for the blending function immediately implies that the functions 
are piecewise polynomials of degree 
and that the breaks between pieces occur at the knots
.
In view of above recursion formula, the Uniform Bspline blending functions 
of order 
over the interval
, together with the properties [10], can be defined in Equation (2).
The blending functions must satisfy the following properties:
• The blending functions are translates of each other, that is,
.
• The blending functions are a partition of unity, that is,
.
• 
for all t.
• The functions 
have continuous 
derivatives, that is, they are 
-continuous.
(2)
The masks 
of the proposed quaternary 
-point scheme can be calculated using the following recurrence relation
(3)
where 
is a uniform B-spline basis function of degree
. In the following, some examples are considered to produce the masks of 2-point, 3-point and 4-point quaternary approximating schemes after setting 
and 4, respectively, in recurrence relation (3).
The 2-point scheme: To obtain the mask of quarternary 2-point scheme, set 
in above relation (3). It may be noted that the linear uniform B-spline basis function 
produces the mask of 2-point quarternary scheme (which is also called corner cutting scheme). Thus 2-point scheme (after adjusting the mask) to refine the control polygon is defined as follows:
(4)
Now, the convergence and smoothness of the proposed 2-point scheme can be analyzed using the Laurent polynomial method introduced by Tang et al. [11].
Theorem 2.1: The quaternary 2-point approximating subdivision scheme converges and has smoothness
.
Proof. To prove that the subdivision scheme 
corresponding to the symbol 
is
. So, the Laurent polynomial 
for the mask of the scheme can be written as
(5)
The Laurent polynomial method is used to prove the smoothness of the scheme to be
. Taking
where
and
With a choice of 
and
, it can be written as
Since the norm of subdivision 
is
therefore 
is contractive, by Theorem 3, and so 
is convergent.
In order to prove the scheme developed to be
, consider 
and
; it can be written as
Since the norm of subdivision 
is
therefore 
is contractive. Consequently, 
is convergent and
.
The 3-point scheme: To obtain the mask of quarternary univariate 3-point scheme, set 
in recursion relation (3). The quadratic uniform B-spline basis functions 
are obtained. The mask 
of the proposed quaternary 3-point scheme can be calculated from these basis functions. The 3-point scheme (after adjusting the mask), to refine the control polygon, is defined as:
(6)
Theorem 2.2: The quaternary 3-point approximating subdivision scheme converges and has smoothness
.
Proof. The smoothness of the above subdivision scheme can be calculated following the same procedure.
The 4-point scheme: Now, a 4-point quaternary scheme is presented and masks of the scheme can be calculated from the cubic basis function. After setting 
in relation (3) the cubic B-spline basis functions 
can be calculated. Thus, 4-point scheme is defined as follows
(7)
Theorem 2.3: The quaternary 4-point approximating subdivision scheme converges and has smoothness
.
Proof. The smoothness of the above subdivision scheme can be calculated following the same procedure.
In the following section the polynomial reproduction property has been discussed.
3. Properties
The polynomial reproduction property has its own importance. As, the reproduction property of the polynomials up to certain degree 
implies that the scheme has 
approximation order. For this, polynomial reproduction can be made from initial date which has been sampled from some polynomial function. In view of [12], the polynomial reproduction property of the proposed scheme can be obtained after having the parametrization 
and definitions in the following manner.
Definition 3.1: For quaternary subdivision scheme the parametrization 
the corresponding parametric shift and attach the data 
for 
to the parameter values
(8)
Definition 3.2: A quaternary subdivision scheme reproduces polynomial of degree 
if it is convergent and its continuous limit function (for any polynomial
) is equal to 
and initial data
Theorem 3.3: A convergent quaternary subdivision scheme reproduces polynomials of degree 
with respect to the parametrization defined in (8) if and only if
Proof. The induction over 
can be performed to prove this theorem following [12].
In view of [12], the following proposition helps to find the necessary conditions defined in (9).
Proposition 3.4: Let 
and
. Then a subdivision symbol 
satisfies
(9)
if and only if 
satisfies
(3)
(
derivative of the symbol) which in turn is equivalent to require that 
for some c(z).
Proposition 3.5: Let a quaternary subdivision scheme that reproduces polynomial up to degree
. Then the smoothed scheme 
with the symbol
satisfies the conditions
and hence generates polynomial of degree
, but it has only linear reproduction.
Proof. Following [12], for some Laurent polynomial
with
, we have
and the fact
. Thus, the 
derivative of 
is
and correct parametric shift for 
is
The 
derivative of 
is
which produces
after simplification, it can be yielded that
.
Hence, it does not reproduce polynomials of degree
.
4. Conclusion
A quaternary univariate 
point (for any integer
) approximating subdivision scheme has been developed which generates the smooth limiting curves. The construction of the quaternary scheme is associated with an algorithm of uniform B-spline basis functions developed from the Cox-de Boor recursion formula. The objective is to introduce the quaternary subdivision schemes, which have smaller support and higher smoothness, comparing to binary and ternary schemes. Moreover the polynomial reproduction property has also been discussed.