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
![](https://www.scirp.org/html/2-1100220\23050019-0e4c-45c0-b96a-a09d6c5527db.jpg)
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
![](https://www.scirp.org/html/2-1100220\910ed386-4548-4a02-8aa1-e0f6e2baaefe.jpg)
It follows that the symbol of a convergent subdivision scheme satisfies the conditions
and
for
.
Introducing a symbol called the Laurent polynomial
![](https://www.scirp.org/html/2-1100220\74276503-5ccc-48d8-8e64-865534fa6bc7.jpg)
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
![](https://www.scirp.org/html/2-1100220\b96a9076-86a6-4e3e-969f-aa9f2bb8130e.jpg)
subdivision
with symbol
is related to S with symbol
, where
and satisfying the property
![](https://www.scirp.org/html/2-1100220\8c7c35c8-f293-47e2-97f6-3c70cec86a65.jpg)
where
and
The norm ![](https://www.scirp.org/html/2-1100220\fff0d4f7-bd69-43a0-a728-5afba41d6ed0.jpg)
of a subdivision scheme
with a mask
is defined by
![](https://www.scirp.org/html/2-1100220\e7408f8e-b3f6-4448-a60c-2ae07cc99d05.jpg)
and
![](https://www.scirp.org/html/2-1100220\cc677a5c-31b8-4b0e-ba00-8470646e5316.jpg)
where
![](https://www.scirp.org/html/2-1100220\283b86e0-8b11-4600-b8f8-599db5b1cf53.jpg)
where
![](https://www.scirp.org/html/2-1100220\4084c198-4dc6-42cf-a776-cdfbcdd64766.jpg)
and
![](https://www.scirp.org/html/2-1100220\942d8778-2eae-439d-95b1-9e501cc2c1a9.jpg)
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
![](https://www.scirp.org/html/2-1100220\5531eabd-a56b-4715-8c3d-b7cdadd5150c.jpg)
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
![](https://www.scirp.org/html/2-1100220\2818bb3e-39d7-471e-b044-bc6225162e1c.jpg)
where
![](https://www.scirp.org/html/2-1100220\bd49165a-9e35-4f4f-9f18-42352f36a53e.jpg)
and
![](https://www.scirp.org/html/2-1100220\d578abeb-4b00-45fd-a263-fba6122e8146.jpg)
With a choice of
and
, it can be written as
![](https://www.scirp.org/html/2-1100220\7f7cbea6-93f4-4c65-bdf0-fa6e96f367d4.jpg)
Since the norm of subdivision
is
![](https://www.scirp.org/html/2-1100220\6b32507f-3ec6-472f-94ec-1cf083b0c4f9.jpg)
therefore
is contractive, by Theorem 3, and so ![](https://www.scirp.org/html/2-1100220\e55f50de-09e6-4dda-9c42-a9ed5c50b59e.jpg)
is convergent.
In order to prove the scheme developed to be
, consider
and
; it can be written as
![](https://www.scirp.org/html/2-1100220\a611fed3-7579-4973-a7cf-9d98e7db7e77.jpg)
Since the norm of subdivision
is
![](https://www.scirp.org/html/2-1100220\18d489f5-9151-48c1-9d2e-3baea6b990d0.jpg)
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
![](https://www.scirp.org/html/2-1100220\69687772-1285-4019-b9db-7f0a60126de9.jpg)
Theorem 3.3: A convergent quaternary subdivision scheme reproduces polynomials of degree
with respect to the parametrization defined in (8) if and only if
![](https://www.scirp.org/html/2-1100220\143b831e-4ee3-45b8-87a6-4a5a4b92d505.jpg)
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
![](https://www.scirp.org/html/2-1100220\f97a3c57-0ea5-4dc4-9523-5f6097d59131.jpg)
and hence generates polynomial of degree
, but it has only linear reproduction.
Proof. Following [12], for some Laurent polynomial
with
, we have
![](https://www.scirp.org/html/2-1100220\fbb76bbd-cb45-47bc-98fe-399235561160.jpg)
and the fact
. Thus, the
derivative of
is
![](https://www.scirp.org/html/2-1100220\d2f423f4-be2e-4390-b535-0f8aca0b57b3.jpg)
and correct parametric shift for
is
![](https://www.scirp.org/html/2-1100220\37ca0d94-8c9e-4890-b30b-67e447f552a7.jpg)
The
derivative of
is
![](https://www.scirp.org/html/2-1100220\0ced5368-8b56-4223-a083-8e1a70b37586.jpg)
which produces
![](https://www.scirp.org/html/2-1100220\39205402-2276-4222-beac-cdd3a32064df.jpg)
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.