# A non-uniform corner-cutting subdivision scheme with an improved accuracy

Byeongseon Jeong §, Hyoseon Yang †, and Jungho Yoon ‡ § Institute of
Mathematical Sciences, Ewha Womans University, Seoul 03760, South Korea
<EMAIL_ADDRESS> † Department of Computational Mathematics, Science
and Engineering, Michigan State University, East Lansing, MI 48824, USA
<EMAIL_ADDRESS>corresponding author)  ‡ Department of Mathematics, Ewha
Womans University, Seoul 03760, South Korea<EMAIL_ADDRESS>
###### Abstract

The aim of this paper is to construct a new non-uniform corner-cutting (NUCC)
subdivision scheme that improves the accuracy of the classical (stationary and
nonstationary) methods. The refinement rules are formulated via the
reproducing property of exponential polynomials. An exponential polynomial has
a shape parameter so that it may be adapted to the characteristic of the given
data. In this study, we propose a method of selecting the shape parameter, so
that it enables the associated scheme to achieve an improved approximation
order (that is, three), while the classical methods attain the second order
accuracy. An analysis of convergence and smoothness of the proposed scheme is
conducted. The proposed scheme is shown to have the same smoothness as the
classical Chaikin’s corner-cutting algorithm, that is, $C^{1}$. Finally, some
numerical examples are presented to demonstrate the advantages of the new
corner-cutting algorithm.

###### keywords:

Corner-cutting Scheme, Exponential B-spline, Nonuniform Subdivision,
Approximation Order

##  1 Introduction

Subdivision schemes are recursive processes of generating smooth curves or
surfaces from a given sequence of control points. By applying a set of
refinement rules to an initial sequence of points iteratively, a subdivision
scheme computes denser sequences of points under a suitable convergence
criteria. Due to the algorithmic efficiency in geometric modeling and design,
subdivision schemes are extensively studied and utilized in many research
fields such as computer-aided geometric design, computer graphics, image
processing, scientific computing etc. General discussions on subdivision
schemes may be found in the references [3, 17, 21].

The smoothness and approximation order of limit functions obtained by the
recursive refinement process are two key features of a convergent subdivision
scheme. They are strongly related to the generation or reproduction properties
of a class of functions such as a set of algebraic polynomials [3, 4, 6, 8,
10, 14, 18, 30] and exponential polynomials [19, 22, 31]. Mostly well-known
subdivision schemes based on algebraic polynomials are the B-spline [4, 8] and
Delauriers-Dubuc interpolatory schemes [14], which respectively provide
optimal smoothness and approximation order. Recent studies have reported that
exponential polynomials are useful and effective in designing and
approximating various geometric shapes. The refinement rules of the associated
subdivision scheme are level-dependent, in which case we call the scheme
nonstationary. Since the earlier works as [19, 22, 31] on exponential
B-splines, important theoretical progress has been achieved during the last
two decades, especially in regards to the reproducing and generation
properties of exponential polynomials [7, 24, 27] and the construction of
wavelets [29, 34, 35]. Also, important practical subdivision algorithms have
been reported. The readers are referred to [1, 11, 12, 13, 22, 26, 28]) and
the references therein.

The quadratic B-spline, known as Chaikin’s corner-cutting algorithm [5], is
one of the most popular and fundamental scheme with various extensions and
applications [2, 15, 16, 25, 32, 33]. The exponential B-spline scheme of
degree $2$ is its natural nonstationary extension. It has advantages because
it can reproduce geometrically important shapes in CAGD. Such merits are
attributed to the ability to reproduce exponential polynomials. At this point,
one should notice that an exponential polynomial has a shape parameter that
can be tuned to the characteristic of the given data. Thus, the final
approximation may be more faithful to the data initially given. Motivated by
this observation, this study aims to introduce a new non-uniform corner-
cutting algorithm that generalizes the exponential B-spline of degree 2. In
particular, we propose an optimal method of selecting the shape parameter in
the exponential polynomial, so that the proposed scheme achieves the improved
approximation order (that is, three), while the classical corner-cutting
(stationary and nonstationary) methods have the second order accuracy. (e.g.,
see [27, 30]). Further, we show that the proposed scheme provides the same
smoothness (that is, $C^{1}$) as the classical Chaikin’s corner-cutting
algorithm. Finally, some numerical examples are presented to demonstrate the
advantages of the new scheme.

The remaining contents of this study are organized as follows. Section 2 is
devoted to provide some basic concepts of (non-uniform) subdivision schemes
and related basic notions. In Section 3, the new subdivision masks are
constructed via the local reproducing property of exponential polynomials,
along with a method for selecting the shape parameter in the exponential
polynomial. The convergence and smoothness of the proposed scheme are
investigated in Section 4. Also, in Section 5, we analyze its approximation
order. Finally, some numerical examples supporting the theoretical results are
presented in Section 6.

##  2 Preliminaries

In this section we present some necessary notation and background material.
Let $\mathbb{Z}$ be the set of all integers, and denote by $\mathbb{Z}_{+}$
the set of nonnegative integers. For a given sequence
${\mathbf{f}}^{k}:=\\{{\mathbf{f}}^{k}_{j}:j\in\mathbb{Z}\\}$, the refinement
rule of a non-uniform subdivision scheme $\\{S_{k}:k\in\mathbb{Z}_{+}\\}$ is
defined by

$\displaystyle{\mathbf{f}}^{k+1}_{2j+\nu}:=S_{k}{\mathbf{f}}^{k}_{2j+\nu}:=\sum_{i\in\mathbb{Z}}{\mathbf{a}}^{j,k}_{2i+\nu}{\mathbf{f}}^{k}_{j-i},\quad\nu=0,1.$
(1)

This can be written formally as ${\mathbf{f}}^{k+1}:=S_{k}{\mathbf{f}}^{k}$.
The sequence ${\mathbf{a}}^{j,k}:=\\{{\mathbf{a}}^{j,k}_{n}:n\in\mathbb{Z}\\}$
is called the subdivision mask and is assumed to be finitely supported. In
fact, some fundamental characteristics of a subdivision are embedded in its
symbol associated with the mask ${\mathbf{a}}^{j,k}$:

$\displaystyle a^{j,k}(z):=\sum_{n\in\mathbb{Z}}{\mathbf{a}}^{j,k}_{n}z^{n}.$

Since the mask ${\mathbf{a}}^{j,k}$ is finitely supported, the symbol
$a^{j,k}(z)$ becomes a Laurent polynomial. The norm of a subdivision operator
$S_{k}$ associated with the refinement masks
$\\{{\mathbf{a}}^{j,k}:j\in\mathbb{Z}\\}$ is defined by

$\displaystyle\|S_{k}\|_{\infty}=\sup_{j\in\mathbb{Z}}\Big{\\{}\sum_{i\in\mathbb{Z}}|{\mathbf{a}}^{j,k}_{2i+\nu}|:\nu=0,1\Big{\\}}.$

It is of necessity to recall the concept of parametrization for a subdivision
scheme. For each level $k$, the value ${\mathbf{f}}^{k}_{j}$ can be attached
to a grid point value $t^{k}_{j}:=2^{-k}j$ or $2^{-k}(j-1/2)$, which are
respectively called primal and dual parametrization. The value $k$ indicates
the scale parameter while $j-\frac{1}{2}$ (or $j$) stands for the location
parameter. For a given parametrization $\\{t^{k}_{j}\\}$, a subdivision scheme
$\\{S_{k}\\}$ is convergent if for any initial data ${\mathbf{f}}^{0}$, there
exists a function $f\in C(\mathbb{R})$ such that for any compact subset
$\Omega$ of $\mathbb{R}$,

$\displaystyle\lim_{k\to\infty}\sup_{j\in\mathbb{Z}\cap
2^{k}\Omega}|{\mathbf{f}}^{k}_{j}-f(t^{k}_{j})|=0$

and $f\not\equiv 0$ for some ${\mathbf{f}}^{0}$. Also, a subdivision scheme
$\\{S_{k}\\}$ is said to be stable if there exists a constant $C>0$ such that
for any ${\mathbf{f}}\in\ell^{\infty}(\mathbb{Z})$,

$\displaystyle\sup_{k,n\in\mathbb{Z}_{+}}\|S_{k+n}\cdots
S_{k}{\mathbf{f}}\|_{\infty}\leq C\|{\mathbf{f}}\|_{\infty}.$

In this study, the term ‘reproduction’ is used to indicate the capability of a
subdivision scheme of reproducing the functions from which the initial
sequence of data values are sampled. Below, we specify the definition of
exponential polynomial reproduction.

######  Definition 2.1.

Let $\mathbb{E}$ be a space of exponential polynomials. We say that a
subdivision scheme $\\{S_{k}\\}$ reproduces the functions in $\mathbb{E}$ if
for the initial data ${\mathbf{f}}^{0}:=\\{f(t^{0}_{j}):j\in\mathbb{Z}\\}$
with $f\in\mathbb{E}$, each sequence ${\mathbf{f}}^{k}:=S_{k-1}\cdots
S_{0}{\mathbf{f}}^{0}$ with $k\geq 1$ satisfies the relation
${\mathbf{f}}^{k}_{j}=f(t^{k}_{j})$ for any $j\in\mathbb{Z}$.

It is well-known that the exponential B-splines can reproduce at most two
exponential polynomials if a suitable normalization factor is taken. Hence,
this study is focused on the following type of space

$\mathbb{E}_{2}:={\rm span}\\{\varphi_{0},\varphi_{1}\\},$

where $\varphi_{0}$ and $\varphi_{1}$ are linearly independent exponential
polynomials. A basic requirement for $\\{\varphi_{0},\varphi_{1}\\}$ is that
its Wronskian matrix at $\vartheta=0$ is invertible, that is,

${\rm det}\big{(}\varphi^{(\beta)}_{\alpha}(0):\alpha,\beta=0,1\big{)}\not=0.$

It is clear that if this condition is satisfied, then the functions
$\varphi_{0}$ and $\varphi_{1}$ are linearly independent.

In addition, for later use, we introduce some notations. For a given sequence
${\mathbf{f}}^{k}:=\\{{\mathbf{f}}^{k}_{j}:j\in\mathbb{Z}\\}$ with density
$2^{-k}$, $\Delta{\mathbf{f}}^{k}$ indicates its second-order difference
defined by

$\Delta{\mathbf{f}}^{k}_{j}:=2^{2k}({\mathbf{f}}^{k}_{j-1}-2{\mathbf{f}}^{k}_{j}+{\mathbf{f}}^{k}_{j+1}).$

Also, denote
$\nabla{\mathbf{f}}^{k}_{j+1}=2^{k}({\mathbf{f}}^{k}_{j+1}-{\mathbf{f}}^{k}_{j})$.
In addition, letting ${\mathbf{f}}^{0}$ be the initial sequence of data, put
${\mathbf{d}}^{0}=\Delta{\mathbf{f}}^{0}$, and then, for each refinement level
$k\in\mathbb{N}$, ${\mathbf{d}}^{k}$ is defined as

$\displaystyle{\mathbf{d}}^{k}:=S^{k}_{a}{\mathbf{d}}^{0}=S^{k}_{a}\Delta{\mathbf{f}}^{0},$
(2)

where $S_{a}$ is the subdivision of the B-spline of degree $2$, i.e., the
classical corner-cutting method.

##  3 Nonuniform corner-cutting subdivision scheme

The objective of this section is to construct a novel non-uniform corner-
cutting (referred to as ‘NUCC’) subdivision scheme. The new subdivision masks
are defined via the property of reproducing two exponential polynomials
$\\{\varphi_{0},\varphi_{1}\\}$ based on the dual parametrization. The
exponential polynomials $\\{\varphi_{0},\varphi_{1}\\}$ and the internal shape
parameter are adjusted by reflecting the local data feature to improve the
accuracy. To this end, for a given data ${\mathbf{f}}^{k}_{i}$ at level $k$,
we assume without great loss that ${\mathbf{f}}^{k}_{i}$ and
$\nabla{\mathbf{f}}^{k}_{i+1}$ do not vanish simultaneously. If this is not
the case, one may put the internal shape parameter as zero, then the scheme
becomes the classical corner-cutting method.

$\bullet$ Non-uniform Subdivision Mask. For a given sequence of data
${\mathbf{f}}^{k}$ at level $k$, we first assume that ${\mathbf{f}}^{k}_{j}$
are nonzero (practically, away from zero). The subdivision mask
${\mathbf{a}}^{j,k}:=\\{{\mathbf{a}}^{j,k}_{n}:n\in\mathbb{Z}\\}$ is
formulated via the reproducing property of two exponential polynomials
$\\{\varphi_{0},\varphi_{1}\\}$ at the evaluation point, say
$\overline{t}:=t^{k+1}_{\ell}$ (where $\ell=2j,2j+1$). According to the parity
of location $\ell$, we determine the two sets of nonzero coefficients: even
mask $\\{{\mathbf{a}}^{j,k}_{-2},\ {\mathbf{a}}^{j,k}_{0}\\}$ and odd mask
$\\{{\mathbf{a}}^{j,k}_{-1},\ {\mathbf{a}}^{j,k}_{1}\\}$. To derive the even
mask, consider the following local reproduction property of the two
exponential functions $\\{\varphi_{0},\varphi_{1}\\}$:

$\displaystyle\mathcal{L}_{0}(\overline{t})\varphi_{n}(t^{k}_{j})+\mathcal{L}_{1}(\overline{t})\varphi_{n}(t^{k}_{j+1})=\varphi_{n}(\overline{t}),\quad
n=0,1.$ (3)

where $\mathcal{L}_{0}$ and $\mathcal{L}_{1}$ are the Lagrange functions in
the space $\mathbb{E}_{2}={\rm span}\\{\varphi_{0},\varphi_{1}\\}$.
Representing this linear system explicitly yields the matrix form

$\displaystyle\begin{bmatrix}\varphi_{0}(t^{k}_{j})&\varphi_{0}(t^{k}_{j+1})\\\
\varphi_{1}(t^{k}_{j})&\varphi_{1}(t^{k}_{j+1})\\\
\end{bmatrix}\begin{bmatrix}\mathcal{L}_{0}(\overline{t})\\\
\mathcal{L}_{1}(\overline{t})\end{bmatrix}=\begin{bmatrix}\varphi_{0}(\overline{t})\\\
\varphi_{1}(\overline{t})\end{bmatrix}.$

The even mask of the proposed subdivision scheme (associated to the location
$\overline{t}$) is defined as the solution of this linear system. To be more
precise, letting $\overline{t}:=t^{k+1}_{2j}$ be an evaluation point at level
$k+1$, we select

$\\{\varphi_{0},\varphi_{1}\\}:=\\{\exp\big{(}\gamma_{2j}(\cdot-\overline{t})\big{)},\exp\big{(}-\gamma_{2j}(\cdot-\overline{t})\big{)}\\},$

where $\gamma_{2j}$ is real or pure imaginary. Then the solution of the above
linear system can be formulated specifically as

$\displaystyle{\mathbf{a}}^{j,k}_{0}:=\mathcal{L}_{0}(\overline{t})=\frac{\sinh(\frac{3}{4}\gamma_{2j}2^{-k})}{\sinh(\gamma_{2j}2^{-k})},\quad{\mathbf{a}}^{j,k}_{-2}:=\mathcal{L}_{1}(\overline{t})=\frac{\sinh(\frac{1}{4}\gamma_{2j}2^{-k})}{\sinh(\gamma_{2j}2^{-k})}.$
(4)

The odd mask is defined in a similar way. Letting
$\overline{t}=t^{k+1}_{2j+1}$, we consider the reproduction of two exponential
functions
$\\{\varphi_{0},\varphi_{1}\\}=\\{\exp\big{(}\gamma_{2j+1}(\cdot-\overline{t})\big{)},\exp\big{(}-\gamma_{2j+1}(\cdot-\overline{t})\big{)}\\}$.
Under this setting, the odd mask is also formulated as the solution of the
linear system (3):

$\displaystyle{\mathbf{a}}^{j,k}_{1}=\frac{\sinh(\frac{1}{4}\gamma_{2j+1}2^{-k})}{\sinh(\gamma_{2j+1}2^{-k})},\quad{\mathbf{a}}^{j,k}_{-1}=\frac{\sinh(\frac{3}{4}\gamma_{2j+1}2^{-k})}{\sinh(\gamma_{2j+1}2^{-k})}.$
(5)

As a conclusion, the new subdivision mask is of the form

$\displaystyle{\mathbf{a}}^{j,k}=\Big{\\{}\frac{\sinh(\frac{1}{4}\gamma_{2j}2^{-k})}{\sinh(\gamma_{2j}2^{-k})},\
\frac{\sinh(\frac{3}{4}\gamma_{2j+1}2^{-k})}{\sinh(\gamma_{2j+1}2^{-k})},\
\frac{\sinh(\frac{3}{4}\gamma_{2j}2^{-k})}{\sinh(\gamma_{2j}2^{-k})},\
\frac{\sinh(\frac{1}{4}\gamma_{2j+1}2^{-k})}{\sinh(\gamma_{2j+1}2^{-k})}\Big{\\}}.$
(6)

In this study, we especially suggest to choose the shape parameter
$\gamma_{2j+\nu}$ for $\nu\in\\{0,1\\}$ as

$\displaystyle\gamma_{2j+\nu}:=\gamma_{2j+\nu,k}:=\sqrt{\frac{{\mathbf{d}}^{k}_{j+\nu}}{{\mathbf{f}}^{k}_{j+\nu}+\epsilon}},\qquad{\rm
sign}({\mathbf{f}}^{k}_{j})={\rm sign}(\epsilon)$ (7)

where a nonzero number $\epsilon$ is employed to prevent the denominator
becoming too small or zero.

######  Remark 3.1.

Suppose that the initial data values are sampled from a smooth function $f$.
Let $\overline{t}=t^{k+1}_{2j+\nu}$ be an evaluation point at level $k+1$. It
can be easily deduced from (7) that

$\gamma^{2}_{2j+\nu}\approx{\frac{f^{\prime\prime}(\overline{t})}{f(\overline{t})}}.$

We will see later that this choice of the shape parameter enables the proposed
scheme to provide improved order of accuracy. For better readability of this
paper, the specific discussion on the motivation for this choice
$\gamma_{2j+\nu}$ is postponed to Section 5.

######  Remark 3.2.

We suggest to choose the non-zero value $\epsilon$ depending on the density of
the given initial data. For instance, one may put $\epsilon$ as
$|\epsilon|=2^{-2k_{0}}$. Accordingly, the shape parameter $\gamma_{j}$ can be
uniformly bounded independent of $j$.

This study is mainly focused on the mask in (6). However, the denominator in
(7) is zero or very small, the refinement rule may be amended as below.

$\bullet$ Alternative Approach. If ${\mathbf{f}}^{k}_{j+\nu}$ ($\nu=0,1$) is
zero or very close to zero, an alternative way to construct the subdivision
masks is given as follows. Let $\overline{t}=t^{k+1}_{2j+\nu}$ be the grid
point associated to ${\mathbf{f}}^{k+1}_{2j+\nu}$. Then we consider the space
of exponential polynomials

$\mathbb{E}_{2}={\rm span}\\{1,\exp(\gamma_{2j+\nu}(\cdot-\overline{t}))\\}$

and then select the shape parameter as

$\displaystyle\gamma_{2j+\nu}:=\gamma_{2j+\nu,k}:={\frac{{\mathbf{d}}^{k}_{j+\nu}}{\nabla{\mathbf{f}}^{k}_{j+1}+\epsilon}},\qquad\nabla{\mathbf{f}}^{k}_{j+1}=2^{k}({\mathbf{f}}^{k}_{j+1}-{\mathbf{f}}^{k}_{j}).$
(8)

Accordingly, by following the same technique as above, the new subdivision
mask can be derived as the form

$\displaystyle{\mathbf{a}}^{j,k}_{-2}=\frac{e^{\gamma_{2j}\frac{1}{4}2^{-k}}-1}{e^{\gamma_{2j}2^{-k}}-1},\quad{\mathbf{a}}^{j,k}_{-1}=\frac{e^{\gamma_{2j+1}\frac{3}{4}2^{-k}}-1}{e^{\gamma_{2j+1}2^{-k}}-1},\quad{\mathbf{a}}^{j,k}_{0}=1-{\mathbf{a}}^{j,k}_{-2},\quad{\mathbf{a}}^{j,k}_{1}=1-{\mathbf{a}}^{j,k}_{-1}.$
(9)

One should note that the above even and odd rules satisfy the partition of
unity, respectively. Hence, for later use, it is necessary to remark that its
Laurent polynomial $a^{j,k}(z)$ satisfies the equations

$a^{j,k}(1)=\sum_{n\in\mathbb{Z}}{\mathbf{a}}^{j,k}_{n}=2,\qquad
a^{j,k}(-1)=\sum_{n\in\mathbb{Z}}{\mathbf{a}}^{j,k}_{n}(-1)^{n}=0.$ (10)

######  Remark 3.3.

It is obvious that the mask ${\mathbf{a}}^{j,k}$ converges to ${\bf
a}=\\{\frac{1}{4},\frac{3}{4},\frac{3}{4},\frac{1}{4}\\}$, as $k\to\infty$,
which is the mask of B-spline of degree $2$ (known as Chaikin’s corner cutting
method). If ${\mathbf{d}}^{k}_{j}$ is zero, then the NUCC scheme turns out to
be the corner-cutting method. So, the NUCC method is nonlinear and it can be
understood as a perturbation of the Chaikin’s corner-cutting algorithm. In
this regard, without great loss, we assume throughout this paper that

$-\frac{1}{4}+{\bf a}_{n}<{\mathbf{a}}^{j,k}_{n}<{\bf a}_{n}+\frac{1}{4}$

for the mask ${\mathbf{a}}_{n}$ of the Chaikin’s algorithm.

##  4 Analysis of convergence and smoothness

In this section, we discuss the convergence and the smoothness of the NUCC
scheme $\\{S_{k}\\}$ with the masks defined in (6). Our specific goal is to
prove that the scheme $\\{S_{k}\\}$ generates $C^{1}$ limit curves. Our
analysis basically relies on the concept of the ‘asymptotic equivalence’
relation between two subdivision schemes.

######  Definition 4.1.

A non-uniform subdivision scheme $\\{S_{k}\\}$ with the mask
$\\{{\mathbf{a}}^{j,k}_{n}\\}$ is said to be asymptotically equivalent to a
uniform stationary scheme $S$ with the mask $\\{{\mathbf{a}}_{n}\\}$ if

$\displaystyle\sum_{k\in\mathbb{Z}_{+}}\sup_{j\in\mathbb{Z}}\sum_{n\in\mathbb{Z}}|{\mathbf{a}}^{j,k}_{n}-{\mathbf{a}}_{n}|<\infty.$
(11)

Based on this concept, we first show that the NUCC scheme is stable and
convergent. To do this, we cite a result [23, Proposition 3.2].

######  Lemma 4.2.

[23] Suppose that a non-uniform subdivision scheme $\\{S_{k}\\}$ is
asymptotically equivalent to a uniform stationary scheme $S$. If $S$ is stable
and convergent, then so is the scheme $\\{S_{k}\\}$.

######  Theorem 4.3.

The NUCC scheme $\\{S_{k}\\}$ is stable and convergent, that is $C^{0}$.

###### Proof.

Using the Maclaurin series expansion of $\sinh(\gamma x)$ which appears in the
explicit form of the mask ${\mathbf{a}}^{j,k}_{n}$ in (6), it is clear that

$\displaystyle|{\mathbf{a}}^{j,k}_{n}-{\mathbf{a}}_{n}|\leq
c\gamma_{2j+\nu}^{2}2^{-2k},\quad\forall j\in\mathbb{Z},\quad\nu=0,1$ (12)

for the mask ${\mathbf{a}}_{n}$ of the quadratic B-spline scheme. In view of
the discussion in Remark 3.2, $\gamma_{2j+\nu}$ is uniformly bounded. Hence,
the relation (11) is readily satisfied. Similarly, we can prove
$|{\mathbf{a}}^{j,k}_{n}-{\mathbf{a}}_{n}|\leq c\gamma_{2j+\nu}2^{-k}$ for the
mask in (9). It ensures that the NUCC scheme $\\{S_{k}\\}$ is asymptotically
equivalent to the quadratic B-spline scheme $S_{\mathbf{a}}$. Since
$S_{\mathbf{a}}$ is stable and convergent, by Lemma 4.2, the scheme
$\\{S_{k}\\}$ is also stable and convergent. ∎

To analyze the smoothness of a scheme $\\{S_{k}\\}$, we use the so-called
‘Property A’ introduced in [23], which is described in terms of the Laurent
polynomial

$\displaystyle
D^{j,k}_{m}(z):=\sum_{\ell=0}^{m}(-1)^{\ell}{m\choose\ell}z^{\ell}a^{j-\ell,k}(z),$
(13)

where $a^{j,k}(z)$ is the symbol associated to the mask
$\\{{\mathbf{a}}^{j,k}_{n}:n\in\mathbb{Z}\\}$.

######  Definition 4.4.

A non-uniform subdivision scheme $\\{S_{k}\\}$ is said to satisfy the Property
A of order m if

$\displaystyle\sum_{k=0}^{\infty}2^{k(m-\alpha)}\Big{|}\frac{d^{\alpha}D^{j,k}_{m}}{dz^{\alpha}}(\pm
1)\Big{|}<\infty,\quad 0\leq\alpha<m.$

A sufficient condition for the smoothness of a non-uniform subdivision scheme
is discussed in [23].

######  Theorem 4.5.

[23] Suppose that a non-uniform binary scheme $\\{S_{k}\\}$ is asymptotically
equivalent to a stationary scheme $S_{a}$. If $\\{S_{k}\\}$ satisfies Property
A of orders $1\leq\ell\leq m$ and $S_{a}$ is a $C^{m}$ scheme with a stable
basic limit function, then $\\{S_{k}\\}$ is also $C^{m}$.

######  Theorem 4.6.

The NUCC scheme $\\{S_{k}\\}$ is $C^{1}$.

###### Proof.

We first prove that the NUCC satisfies Property A of order $1$. To this end,
we need to estimate the Laurent polynomial
$D^{j,k}_{1}(z)=a^{j,k}(z)-za^{j-1,k}(z)$ at $z=-1,1$. Let $a(z)$ be the
symbol of the quadratic B-spline. It follows that

$\displaystyle|D^{j,k}_{1}(\pm 1)|\leq|a^{j,k}(\pm 1)-a(\pm 1)|+|a(\pm 1)-(\pm
1)a^{j-1,k}(\pm 1)|.$

where $a(1)=2$ and $a(-1)=0$. Here, to estimate the above terms, we need to
consider the Laurent polynomial $a^{j,k}(z)$ associated to both of the cases
(6) and (9) respectively. It is easy to see that $a^{j,k}(z)$ of (6) satisfies

$a^{j,k}(\pm 1)=a(\pm 1)+O(2^{-2k}).$

Also, as observed in (10), the mask of the NUCC of (9) satisfies the partition
of unity such that $a^{j,k}(1)=2$ and $a^{j,k}(-1)=0$. So, clearly,
$a^{j,k}(\pm 1)=a(\pm 1)$. Consequently, it is immediate that

$|D^{j,k}_{1}(\pm 1)|\leq c2^{-2k}$

for a constant $c>0$. It verifies that the NUCC scheme fulfills the Property
A. Moreover, as shown in the proof of Theorem 4.3, the NUCC scheme
$\\{S_{k}\\}$ is asymptotically equivalent to the quadratic B-spline
subdivision $S_{a}$. Since $S_{a}$ is $C^{1}$ and its basic limit functions is
stable, by Theorem 4.5, $\\{S_{k}\\}$ is also $C^{1}$. It completes the proof.
∎

######  Remark 4.7.

A bivariate subdivision scheme for modeling surfaces can be easily constructed
via the tensor product of the univariate schemes. Hence, it clearly follows
from [9, Corollary 1] that the tensor product of univariate NUCC schemes is
$C^{1}$.

##  5 Approximation order

This section aims to show that the NUCC scheme $\\{S_{k}\\}$ achieves the
approximation order $3$, while the classical methods provide the second order
accuracy. Suppose that the initial data is of the form
${\mathbf{f}}^{0}=\\{f(2^{-k_{0}}(n-\frac{1}{2})):n\in\mathbb{Z}\\}$ with
$k_{0}\in\mathbb{Z}_{+}$. We shall show that

$\|{\mathbf{f}}^{\infty}-f\|_{\infty}\leq c_{f}2^{-3k_{0}}$

where ${\mathbf{f}}^{\infty}=\lim_{k\to\infty}S_{k}\cdots
S_{0}{\mathbf{f}}^{0}$. This work especially focuses on approximating
functions in the Sobolev space

$W^{r}_{\infty}(\mathbb{R}):=\big{\\{}f:\mathbb{R}\to\mathbb{R}:\|f\|_{r,\infty}:=\sum_{n=0}^{r}\|f^{(n)}\|_{\infty}<\infty\big{\\}}$

for $r\in\mathbb{Z}_{+}.$ Since the proposed scheme is data-dependent, the
techniques commonly used for the proof in the uniform case are not applicable
to our case. Eventually, the technique for this proof is more involved. In
order to facilitate our proof, throughout this section, we use the following
notation. For a given $k\in\mathbb{Z}_{+}$, denote by

$\displaystyle{\hat{\mathbf{f}}}^{k}:=\big{\\{}f(2^{-k_{0}}t^{k}_{j}):j\in\mathbb{Z}\big{\\}}$
(14)

the sequence sampled from a smooth function $f(2^{-k_{0}}\cdot)$ at the $k$th
level grid points $t^{k}_{j}$. In the following lemma, we discuss the
approximation properties of the subdivision operator $S_{k}$ to the sequence
of data ${\hat{\mathbf{f}}}^{k}$.

######  Lemma 5.1.

For a given function $f\in W^{3}_{\infty}(\mathbb{R})$, let
${\hat{\mathbf{f}}}^{k}$ be the sequence of data of the form (14). If
$\\{S_{k}\\}$ is the NUCC scheme acting on the initial data of the form
${\mathbf{f}}^{0}=\\{f(2^{-k_{0}}(n-\frac{1}{2})):n\in\mathbb{Z}\\}$, then we
have

$|S_{k}{\hat{\mathbf{f}}}^{k}_{j}-{\hat{\mathbf{f}}}^{k+1}_{j}|\leq
c_{f}2^{-2k_{0}-k},\quad j\in\mathbb{Z},$ (15)

with a constant $c_{f}>0$ depending on $f$.

###### Proof.

Letting $S_{\mathbf{a}}$ be the subdivision operator of the quadratic B-spline
scheme with the mask ${\mathbf{a}}$, we can express

$\displaystyle\begin{aligned}
S_{k}{\hat{\mathbf{f}}}^{k}_{j}-{\hat{\mathbf{f}}}^{k+1}_{j}=\big{(}S_{k}{\hat{\mathbf{f}}}^{k}_{j}-S_{{\mathbf{a}}}{\hat{\mathbf{f}}}^{k}_{j}\big{)}+\big{(}S_{{\mathbf{a}}}{\hat{\mathbf{f}}}^{k}_{j}-{\hat{\mathbf{f}}}^{k+1}_{j}\big{)}\end{aligned}$
(16)

Since the quadratic B-spline $S_{\mathbf{a}}$ provides the second-order
accuracy for smooth functions and the data ${\hat{\mathbf{f}}}^{k}$ has the
density $2^{-k_{0}-k}$, it holds clearly that
$|S_{{\mathbf{a}}}{\hat{\mathbf{f}}}^{k}_{j}-{\hat{\mathbf{f}}}^{k+1}_{j}|=O(2^{-2(k_{0}+k)})$.
Thus, it remains to estimate the term
$|S_{k}{\hat{\mathbf{f}}}^{k}_{j}-S_{{\mathbf{a}}}{\hat{\mathbf{f}}}^{k}_{j}|$.
From the proof of Theorem 4.3 and Remark 3.2, we have

$\displaystyle|S_{k}{\hat{\mathbf{f}}}^{k}_{j}-S_{{\mathbf{a}}}{\hat{\mathbf{f}}}^{k}_{j}|\leq\|{\mathbf{a}}^{j,k}-{\mathbf{a}}\|_{\infty}\|{\hat{\mathbf{f}}}^{k}\|_{\infty}\leq
c2^{-k}\|{\mathbf{d}}^{k}\|_{\infty}\|{\hat{\mathbf{f}}}^{k}\|_{\infty}$

with a constant $c>0$. By construction,
${\mathbf{d}}^{k}=S^{k}_{\mathbf{a}}\Delta{\mathbf{f}}^{0}$. Since the initial
data ${\mathbf{f}}^{0}$ is sampled from the dilated function
$f(2^{-k_{0}}\cdot)$, it is clear that
$|\Delta{\mathbf{f}}^{0}_{n}|\leq|2^{-2k_{0}}f^{\prime\prime}(2^{-k_{0}}(n-\frac{1}{2}))|+c^{\prime}2^{-3k_{0}}\|f^{\prime\prime\prime}\|_{\infty}$
for some constant $c^{\prime}>0$. It concludes
$|S_{k}{\hat{\mathbf{f}}}^{k}_{j}-S_{{\mathbf{a}}}{\hat{\mathbf{f}}}^{k}_{j}|\leq
c_{f}2^{-2k_{0}-k}$ with $c_{f}>0$ independent of $k$. Hence, we obtain the
lemma’s claim. ∎

######  Lemma 5.2.

Suppose that the initial data
${\mathbf{f}}^{0}:=\\{f(2^{-k_{0}}(n-\frac{1}{2})):n\in\mathbb{Z}\\}$ is
sampled from a function $f\in W^{3}_{\infty}(\mathbb{R})$, and let
${\hat{\mathbf{f}}}^{k}$ be the sequence of data of the form (14). If
${\mathbf{f}}^{k}=S_{k-1}\cdots S_{0}{\mathbf{f}}^{0}$ with the NUCC scheme
$\\{S_{k}\\}$, we obtain

$\displaystyle\|{\mathbf{f}}^{k}-{\hat{\mathbf{f}}}^{k}\|_{\infty}\leq
c_{f}2^{-2k_{0}},$

where $c_{f}>0$ is a positive constant depending on $f$ but independent of
$k_{0}$.

###### Proof.

We can represent ${\mathbf{f}}^{k}$ as the following telescoping sum:

$\displaystyle{\mathbf{f}}^{k}=S_{k-1}{\hat{\mathbf{f}}}^{k-1}+\sum_{\ell=1}^{k-1}S_{k-1}\cdots
S_{k-\ell}(S_{k-\ell-1}{\hat{\mathbf{f}}}^{k-\ell-1}-{\hat{\mathbf{f}}}^{k-\ell}).$

According to Theorem 4.3, the NUCC scheme $\\{S_{k}\\}$ is stable such that
$\|S_{k-1}\cdots S_{k-\ell}\|_{\infty}\leq c$ for any $k$ and $\ell$ with
$k\geq\ell$. It induces the relation

$\displaystyle|{\mathbf{f}}^{k}_{j}-{\hat{\mathbf{f}}}^{k}_{j}|$
$\displaystyle\leq\|S_{k-1}{\hat{\mathbf{f}}}^{k-1}-{\hat{\mathbf{f}}}^{k}\|_{\infty}+\sum_{\ell=1}^{k-1}\|S_{k-1}\cdots
S_{k-\ell}\|_{\infty}\|S_{k-\ell-1}{\hat{\mathbf{f}}}^{k-\ell-1}-{\hat{\mathbf{f}}}^{k-\ell}\|_{\infty}$
$\displaystyle\leq
c\sum_{\ell=0}^{k-1}\|S_{\ell}{\hat{\mathbf{f}}}^{\ell}-{\hat{\mathbf{f}}}^{\ell+1}\|_{\infty}.$

Further, by Lemma 5.1,
$\|S_{\ell}{\hat{\mathbf{f}}}^{\ell}-{\hat{\mathbf{f}}}^{\ell+1}\|_{\infty}\leq
c_{f}2^{-2k_{0}-\ell}$. Hence, it leads to the bound

$\displaystyle\sum_{\ell=0}^{k-1}\|S_{\ell}{\hat{\mathbf{f}}}^{\ell}-{\hat{\mathbf{f}}}^{\ell+1}\|_{\infty}\leq
c_{f}\sum_{\ell=0}^{k-1}2^{-2k_{0}-\ell}\leq
c_{f}\sum_{\ell=0}^{\infty}2^{-2k_{0}-\ell}\leq c^{\prime}_{f}2^{-2k_{0}},$

which finishes the proof. ∎

Based on the above results, we shall investigate the approximation order of
the NUCC scheme. For better readability of this paper, our proof will be done
by focusing on the mask in (6); the other case in (9) can be done similarly.
In advance to proceed further, we introduce some notation. For each
$j\in\mathbb{Z}$ and $\nu=0,1$, we use the abbreviation

$j_{\nu}:=2j+\nu.$

Denote by

$\displaystyle\widehat{{\mathbf{f}}^{\prime\prime}}{}^{k}:=\big{\\{}f^{\prime\prime}(2^{-k_{0}}t^{k}_{j}):j\in\mathbb{Z}\big{\\}}$
(17)

the sequence sampled from a smooth function
$f^{\prime\prime}(2^{-k_{0}}\cdot)$ at the $k$th level grid points
$t^{k}_{j}$. Let $\overline{t}=2^{-k_{0}}t^{k+1}_{j_{\nu}}$ with $\nu=0,1$ be
the evaluation points at level $k+1$ between $2^{-k_{0}}t^{k}_{j}$ and
$2^{-k_{0}}t^{k}_{j+1}$. Then, for a given smooth function $f$, consider an
auxiliary function $Q_{\nu}f$ defined by

$\displaystyle
Q_{\nu}f(t)=\mathcal{L}_{0,\nu}(t)f(2^{-k_{0}}t^{k}_{j})+\mathcal{L}_{1,\nu}(t)f(2^{-k_{0}}t^{k}_{j+1})$
(18)

where $\mathcal{L}_{0,\nu}$ and $\mathcal{L}_{1,\nu}$ are the Lagrange
functions as given in (3) in the exponential space

$\mathbb{E}_{2}:={\rm
span}\\{\exp({\hat{\gamma}}_{j_{\nu}}(\cdot-\overline{t})),\
\exp(-{\hat{\gamma}}_{j_{\nu}}(\cdot-\overline{t}))\\}$ (19)

satisfying $\mathcal{L}_{n,\nu}(t^{k}_{j+\ell})=\delta_{\ell,n}$ for
$\ell,n=0,1$. Here, we suppose that the shape parameter is chosen as

$\displaystyle{\hat{\gamma}}_{j_{\nu}}:={\hat{\gamma}}_{j_{\nu},k}:=\sqrt{\frac{\widehat{{\mathbf{f}}^{\prime\prime}}{}_{j+\nu}^{k}}{{\hat{\mathbf{f}}}^{k}_{j+\nu}}}.$
(20)

where
$\widehat{{\mathbf{f}}^{\prime\prime}}{}^{k}_{j+\nu}:=f^{\prime\prime}(2^{-k_{0}}t^{k}_{j+\nu})$.
It is obvious that

$\widehat{{\mathbf{f}}^{\prime\prime}}{}^{k}_{j+\nu}=f^{\prime\prime}(\overline{t})+O(2^{-k_{0}-k}).$
(21)

Note that the shape parameter $\gamma_{j_{\nu}}$ in the mask of the NUCC
scheme (see (7)) is an approximation to ${\hat{\gamma}}_{j_{\nu}}$. The only
difference is that the shape parameter (20) is given in terms of the original
function values. Further, in view of Section 3, it is obvious that the
operator $Q_{\nu}$ locally reproduces the exponential polynomials in the space
$\mathbb{E}_{2}$.

######  Lemma 5.3.

For each $\nu=0,1$, let $Q_{\nu}f$ be defined as in (18) with $f\in
W^{3}_{\infty}(\mathbb{R})$. Let $\overline{t}:=2^{-k_{0}}t^{k+1}_{j_{\nu}}$
and assume that $|f(t)|\geq\tau$ for $|t-\overline{t}|\leq 2^{-k_{0}-k}$ with
a constant $\tau>0$. Then, we have the estimate

$\displaystyle|Q_{\nu}f(2^{-k_{0}}t^{k+1}_{j_{\nu}})-f(2^{-k_{0}}t^{k+1}_{j_{\nu}})|\leq
c_{f,\tau}2^{-3(k_{0}+k)}$ (22)

for some constant $c_{f,\tau}>0$ depending on $f$ and $\tau$.

###### Proof.

Noting that the space $\mathbb{E}_{2}$ in (19) can be written as
$\mathbb{E}_{2}={\rm
span}\\{\cosh({\hat{\gamma}}_{j_{\nu}}(\cdot-\overline{t})),\
\sinh({\hat{\gamma}}_{j_{\nu}}(\cdot-\overline{t}))\\}$, we define a function
$G_{f}$ by

$\displaystyle
G_{f}=f(\overline{t})\cosh({\hat{\gamma}}_{j_{\nu}}(\cdot-\overline{t}))+f^{\prime}(\overline{t})\frac{\sinh({\hat{\gamma}}_{j_{\nu}}(\cdot-\overline{t}))}{{\hat{\gamma}}_{j_{\nu}}}.$
(23)

Clearly, $G_{f}$ is in the space $\mathbb{E}_{2}$ and approximates $f$ in the
sense that $G_{f}(\overline{t})=f(\overline{t})$ and
$G_{f}^{\prime}(\overline{t})=f^{\prime}(\overline{t})$. Moreover,

$G_{f}^{\prime\prime}(\overline{t})={\hat{\gamma}}^{2}_{j_{\nu}}f(\overline{t})=\frac{\widehat{{\mathbf{f}}^{\prime\prime}}{}^{k}_{j+\nu}}{{\hat{\mathbf{f}}}^{k}_{j+\nu}}f(\overline{t}).$

Then, taking the Taylor expansion of $f-G_{f}$ around $\overline{t}$, it
follows that

$\displaystyle
f(t)-G_{f}(t)=\Big{(}f^{\prime\prime}(\overline{t})-\frac{\widehat{{\mathbf{f}}^{\prime\prime}}{}^{k}_{j+\nu}}{{\hat{\mathbf{f}}}^{k}_{j+\nu}}f(\overline{t})\Big{)}\frac{(t-\overline{t})^{2}}{2}+(f-G_{f})^{(3)}(\xi)\frac{(t-\overline{t})^{3}}{6}.$
(24)

By (21),
$\widehat{{\mathbf{f}}^{\prime\prime}}{}^{k}_{j+\nu}=f^{\prime\prime}(\overline{t})+O(2^{-k_{0}-k})$.
Also, ${\hat{\mathbf{f}}}^{k}_{j+\nu}=f(\overline{t})+O(2^{-k_{0}-k})$. Based
on the definition of ${\hat{\gamma}}_{j_{\nu}}$, some elementary calculation
reveals that $|G_{f}^{(3)}(\xi)|\leq c_{f}$ for some $c_{f}>0$. Since
$|f(t)|\geq\tau$ for $|t-\overline{t}|\leq 2^{-k_{0}-k}$, the identity (24)
leads to the following bound:

$\displaystyle|f(t)-G_{f}(t)|\leq c_{f,\tau}2^{-3(k+k_{0})}$ (25)

with a constant $c_{f,\tau}>0$ depending on $f$ and $\tau$. Now, since $G_{f}$
is in the space $\mathbb{E}_{2}$, due to the exponential reproducing property
of $\mathcal{L}_{0,\nu}$ and $\mathcal{L}_{0,\nu}$, $G_{f}$ is represented as

$G_{f}(\overline{t})=\mathcal{L}_{0,\nu}(\overline{t})G_{f}(2^{-k_{0}}t^{k}_{j})+\mathcal{L}_{1,\nu}(\overline{t})G_{f}(2^{-k_{0}}t^{k}_{j+1}).$

It leads to the expression

$\displaystyle\begin{aligned}
Q_{\nu}f(\overline{t})-f(\overline{t})&=Q_{\nu}f(\overline{t})-G_{f}(\overline{t})\\\
&=\mathcal{L}_{0,\nu}(\overline{t})(f(2^{-k_{0}}t^{k}_{j})-G_{f}(2^{-k_{0}}t^{k}_{j}))+\mathcal{L}_{1,\nu}(\overline{t})(f(2^{-k_{0}}t^{k}_{j+1})-G_{f}(2^{-k_{0}}t^{k}_{j+1})).\end{aligned}$
(26)

Applying the estimate (25) to (26) induces the required result (22). ∎

Using the above results, we will show that the NUCC scheme $\\{S_{k}\\}$ can
provide an improved order of accuracy better than the classical methods.

######  Lemma 5.4.

Let $\\{S_{k}\\}$ be the NUCC scheme acting on the initial data
${\mathbf{f}}^{0}=\\{f(2^{-k_{0}}(n-\frac{1}{2}):n\in\mathbb{Z}\\}$ with a
function $f\in W^{3}_{\infty}(\mathbb{R})$. Let
${\hat{\mathbf{f}}}^{k}=\\{f(2^{-k_{0}}t^{k}_{j}):j\in\mathbb{Z}\\}$ as given
in (14) and $\overline{t}:=2^{-k_{0}}t^{k+1}_{j_{\nu}}$ for $\nu=0,1$. If
$|f(t)|\geq\tau$ for $|t-\overline{t}|\leq 2^{-k_{0}-k}$ with a constant
$\tau>0$, then we get

$\displaystyle|S_{k}{\hat{\mathbf{f}}}^{k}_{j_{\nu}}-{\hat{\mathbf{f}}}^{k+1}_{j_{\nu}}|\leq
c_{f,\tau}2^{-(3k_{0}+2k)},$ (27)

where $c_{f,\tau}>0$ is a constant dependent upon $f$ and $\tau$.

###### Proof.

Using the auxiliary function $Q_{\nu}f$ in (18), let us write

$\displaystyle|S_{k}{\hat{\mathbf{f}}}^{k}_{j_{\nu}}-{\hat{\mathbf{f}}}^{k+1}_{j_{\nu}}|$
$\displaystyle\leq|S_{k}{\hat{\mathbf{f}}}^{k}_{j_{\nu}}-Q_{\nu}f(\overline{t})|+|Q_{\nu}f(\overline{t})-{\hat{\mathbf{f}}}^{k+1}_{j_{\nu}}|.$
(28)

Then we first consider the case $j_{\nu}=2j$, i.e., $\nu=0$. To investigate
the first term in the right-hand side of this inequality, we see that

$\displaystyle
S_{k}{\hat{\mathbf{f}}}^{k}_{2j}-Q_{0}f(\overline{t})=\big{(}{\mathbf{a}}^{i,k}_{0}-\mathcal{L}_{0,0}(\overline{t})\big{)}{\hat{\mathbf{f}}}^{k}_{j}+\big{(}{\mathbf{a}}^{i,k}_{-2}-\mathcal{L}_{1,0}(\overline{t})\big{)}{\hat{\mathbf{f}}}^{k}_{j+1}$
(29)

with the Lagrange functions $\mathcal{L}_{n,0}$ in (18). Recall that the mask
${\mathbf{a}}^{i,k}$ of the NUCC scheme and $\mathcal{L}_{0,0}(\overline{t})$
are written in terms of the function
$\frac{\sinh(\frac{3}{4}\gamma_{t})}{\sinh\gamma t}$ with a suitable $\gamma$
respectively. By using the Maclaurin series expansion argument, we have

$\displaystyle\begin{split}\big{|}\big{(}{\mathbf{a}}^{j,k}_{0}-\mathcal{L}_{0,0}(\overline{t})\big{)}{\hat{\mathbf{f}}}^{k}_{j}\big{|}&\leq
c_{1}\Big{|}\Big{(}\frac{2^{-2k}{\mathbf{d}}^{k}_{j}}{{\mathbf{f}}^{k}_{j}}-\frac{2^{-2(k_{0}+k)}\widehat{{\mathbf{f}}^{\prime\prime}}{}^{k}_{j}}{{\hat{\mathbf{f}}}^{k}_{j}}\Big{)}{\hat{\mathbf{f}}}^{k}_{j}\Big{|}+c_{2}2^{-4(k_{0}+k)}\\\
&=c_{1}2^{-2k}\Big{|}\frac{{\mathbf{d}}^{k}_{j}}{{\mathbf{f}}^{k}_{j}}{\hat{\mathbf{f}}}^{k}_{j}-2^{-2k_{0}}\widehat{{\mathbf{f}}^{\prime\prime}}{}^{k}_{j}\Big{|}+c_{2}2^{-4(k_{0}+k)},\end{split}$
(30)

for some constants $c_{1},c_{2}>0$. Here,
${\mathbf{d}}^{k}=S^{k}_{{\mathbf{a}}}\Delta{\mathbf{f}}^{0}$ and the data
${\mathbf{f}}^{0}$ has the density $2^{-k_{0}}$. So, obviously,

$S^{k}_{{\mathbf{a}}}\Delta{\mathbf{f}}^{0}_{j}=2^{-2k_{0}}f^{\prime\prime}(2^{-k_{0}}t^{k+1}_{2j})+O(2^{-3k_{0}}).$

Also, by (21),
$\widehat{{\mathbf{f}}^{\prime\prime}}{}^{k}_{j}=f^{\prime\prime}(2^{-k_{0}}t^{k+1}_{2j})+O(2^{-k_{0}})$.
Moreover, by Lemma 5.2,
${\mathbf{f}}^{k}_{j}={\hat{\mathbf{f}}}^{k}_{j}+O(2^{-2k_{0}})$. Thus a
direct computation from (30) yields

$\displaystyle\big{|}\big{(}{\mathbf{a}}^{i,k}_{0}-\mathcal{L}_{0,0}(\overline{t})\big{)}{\hat{\mathbf{f}}}^{k}_{j}\big{|}\leq
c_{f,\tau}2^{-3k_{0}-2k}$

for a constant $c_{f,\tau}>0$ depending on $f$ and $\tau$. In a similar way,
we can get
$\big{|}\big{(}{\mathbf{a}}^{i,k}_{-2}-\mathcal{L}_{1,0}(\overline{t})\big{)}{\hat{\mathbf{f}}}^{k}_{j}\big{|}\leq
c_{f,\tau}2^{-3k_{0}-2k}$ which estimates the second term in the right-hand
side of (29). It concludes that

$\displaystyle|S_{k}{\hat{\mathbf{f}}}^{k}_{j}-Q_{0}f(\overline{t})|\leq
c2^{-3k_{0}-2k}.$ (31)

Due to Lemma 5.3, the last term in (28) satisfies
$|Q_{0}f(\overline{t})-{\hat{\mathbf{f}}}^{k+1}_{2j}|\leq
c_{f,\tau}2^{-3(k_{0}+k)}$. This together with the bound (31) implies the
estimate (27). The proof for the case $j_{\nu}=2j+1$ can be done similarly.
So, we finish the proof. ∎

We are now ready to prove our main result.

######  Theorem 5.5.

Let $\\{S_{k}\\}$ be the NUCC scheme acting on the initial data of the form
${\mathbf{f}}^{0}=\\{f(2^{-k_{0}}(n-\frac{1}{2}):n\in\mathbb{Z}\\}$ with a
function $f\in W^{3}_{\infty}(\mathbb{R})$. Put
$\overline{t}=2^{-k_{0}}t^{k+1}_{j}$ be a dyadic point. Then if
$|f(t)|\geq\tau$ with $\tau>0$ for $|t-\overline{t}|\leq 2^{-k_{0}-k}$, then
the limit function ${\mathbf{f}}^{\infty}=\lim_{k\to\infty}S_{k}\cdots
S_{0}{\mathbf{f}}^{0}$ satisfies the estimate

$\displaystyle|{\mathbf{f}}^{\infty}(\overline{t})-f(\overline{t})|\leq
c_{f,\tau}2^{-3k_{0}}$ (32)

for a constant $c_{f,\tau}>0$ dependent upon $f$ and $\tau$ but independent of
$k_{0}$.

###### Proof.

Using the telescoping sum (as in the proof of Lemma 5.2) and applying Lemma
5.4, we can estimate the error between ${\mathbf{f}}^{k+1}$ and
${\hat{\mathbf{f}}}^{k+1}$ as

$\displaystyle\|{\mathbf{f}}^{k+1}-{\hat{\mathbf{f}}}^{k+1}\|_{\infty}\leq
c\sum_{\ell=0}^{k}\|S_{\ell}{\hat{\mathbf{f}}}^{\ell}-{\hat{\mathbf{f}}}^{\ell+1}\|_{\infty}\leq
c_{f,\tau}\sum_{\ell=0}^{k}2^{-(3k_{0}+2\ell)}\leq c_{f,\tau}2^{-3k_{0}}$

for a constant $c_{f,\tau}>0$ depending on $f$ and $\tau$. Since this relation
holds for any dyadic point $t^{k+1}_{j}$, we can obtain the desired result. ∎

######  Corollary 5.6.

Let the initial data be of the form
${\mathbf{f}}^{0}=\\{f(2^{-k_{0}}t^{0}_{n}):n\in\mathbb{Z}\\}$ with $f\in
W^{3}_{\infty}(\mathbb{R})$. Assume that
$\|{\mathbf{f}}^{0}\|_{\infty}\geq\tau$ for some $\tau>0$. Under the same
conditions of Theorem 5.5, we have

$\displaystyle\|{\mathbf{f}}^{\infty}-f\|_{\infty}\leq c_{f,\tau}2^{-3k_{0}}.$

The following theorem treats the local approximation order of the NUCC scheme
for the (alternative) case that is suggested in (9). It can be proved in a
similar fashion to the case of Theorem 5.5.

######  Theorem 5.7.

Let $f\in W^{3}_{\infty}(\mathbb{R})$ and put
$\overline{t}=2^{-k_{0}}t^{k+1}_{j}$ be a dyadic point. Assume that
$|f^{\prime}(t)|\geq\tau$ with $\tau>0$ for $|t-\overline{t}|\leq
2^{-k_{0}-k}$. Then, under the same conditions and assumptions of Theorem 5.5,
we have

$\displaystyle|{\mathbf{f}}^{\infty}(\overline{t})-f(\overline{t})|\leq
c_{f,\tau}2^{-3k_{0}}$ (33)

for a constant $c_{f,\tau}>0$.

###### Proof.

The proof can be done by applying the same technique above. ∎

Figure 1: Limit functions of the classical corner-cutting algorithm (dashed
line) and the proposed scheme (real line), and their first- and second-order
derivatives.

##  6 Numerical examples

In this section, we present some numerical examples to demonstrate the
performance of the NUCC scheme. The first example verifies that the proposed
NUCC scheme is $C^{1}$. It supports the theoretical result in Section 4.

######  Example 6.1.

(Smoothness) In this example, we put the initial data ${\mathbf{f}}^{0}$ as
the Kronecker delta sequence, i.e.,
${\mathbf{f}}^{0}=\\{{\mathbf{f}}^{0}_{j}:=\delta_{j,0}:j\in\mathbb{Z}\\}$
where $\delta_{j,0}$ equals zero, if $j\neq 0$, and one otherwise. In order to
get the limit function, we recursively apply the refinement rule $\\{S_{k}\\}$
to ${\mathbf{f}}^{0}$ using the mask given in (6). In this experiment, we set
$\epsilon$ in the shape parameter $\gamma_{j}$ as $|\epsilon|=1$. We compare
the limit function with the one generated by the classical corner-cutting
algorithm. Figure 1 depicts the two limit functions, and their first- and
second-order derivatives.

Table 1: Comparison of the approximation order to the function defined in (34). Density of initial data |  | Max. Error |  | Approximation Order
---|---|---|---|---
|  | Exp. B-spline | Proposed |  | Exp. B-spline | Proposed
1 |  | 8.6789E-02 | 5.0305E-02 |  |  |
$2^{-1}$ |  | 2.3629E-02 | 6.2276E-03 |  | 1.9 | 3.0
$2^{-2}$ |  | 6.1175E-03 | 6.2632E-04 |  | 1.9 | 3.3
$2^{-3}$ |  | 1.5701E-03 | 7.5863E-05 |  | 2.0 | 3.0
$2^{-4}$ |  | 3.9306E-04 | 9.2633E-06 |  | 2.0 | 3.0
$2^{-5}$ |  | 9.8297E-05 | 1.1537E-06 |  | 2.0 | 3.0
$2^{-6}$ |  | 2.4576E-05 | 1.4397E-07 |  | 2.0 | 3.0
$2^{-7}$ |  | 6.1442E-06 | 1.7986E-08 |  | 2.0 | 3.0
$2^{-8}$ |  | 1.5360E-06 | 2.2479E-09 |  | 2.0 | 3.0
$2^{-9}$ |  | 3.8394E-07 | 2.8126E-10 |  | 2.0 | 3.0

Figure 2: Curve-fitting results: classical corner-cutting method (dashed line)
and the new algorithm with $|\epsilon|=1$ (real line).

The following example treats the approximation order of the NUCC scheme
discussed in Section 5,

######  Example 6.2.

(Approximation order) This example tests the numerical approximation order of
the NUCC scheme for the (scaled one-dimensional Franke) function

$\displaystyle
f(t):=\frac{3}{4}e^{-(\frac{9}{8}t-2)^{2}/4}+\frac{3}{4}e^{-(\frac{9}{8}t+1)^{2}/49}+\frac{1}{2}e^{-(\frac{9}{8}t-7)^{2}/4}-\frac{1}{5}e^{-(\frac{9}{8}t-4)^{2}}.$
(34)

The initial data is sampled from the function $f$ with density $2^{-k_{0}}$
for $k_{0}=0,\ldots,9$. As verified in [27], an exponential B-spline
subdivision can provide the approximation order at most two when a suitable
normalization factor is taken. Thus, we employ the normalized exponential
B-spline scheme of degree $2$ reproducing two exponential polynomials
$\\{\exp(\gamma\cdot),\exp(-\gamma\cdot)\\}$ with $\gamma=1/2$. The
corresponding subdivision masks are given by

$\displaystyle{\mathbf{a}}^{[k]}_{-2}=\frac{\sinh(2^{-k-3})}{\sinh(2^{-k-1})},\quad{\mathbf{a}}^{[k]}_{-1}=\frac{\sinh(3\cdot
2^{-k-3})}{\sinh(2^{-k-1})},\quad{\mathbf{a}}^{[k]}_{0}={\mathbf{a}}^{[k]}_{-1},\quad{\mathbf{a}}^{[k]}_{1}={\mathbf{a}}^{[k]}_{-2}.$

Table 1 displays the experimental results. As one can see in Table 1, the NUCC
scheme achieves the third-order accuracy while the exponential B-spline scheme
attains the second order accuracy.

######  Example 6.3.

(Curve fitting) In this example, we compare the curve-fitting performance of
the classical corner-cutting method and the NUCC algorithm. Figure 2 shows the
resulting curves generated from several initial data. For this experiment, we
used $|\epsilon|=1$. The limit curves of the proposed algorithm better follow
the sharp corners than those of the classical scheme.

Acknowledgements  J. Yoon was supported in part by the National Research
Foundation of Korea under grant NRF-2020R1A2C1A01005894.

## References

  * [1] C. Beccari, G. Casciola, L. Romani, A non-stationary uniform tension controlled interpolating 4-point scheme reproducing conics, Comput. Aided Geom. Design, 24 (2007) 1–9.
  * [2] C. de Boor, Cutting corners always works, Comput. Aided Geom. Design, 4 (1987) 125–131.
  * [3] A. Cavaretta, W. Dahmen, C. A. Micchelli, Stationary Subdivision, Mem. Amer. Math. Soc. 93(453) (1991) 1-186.
  * [4] E. Catmull, J. Clark, Recursively generated B-spline surfaces on arbitrary topological meshes, Comput. Aided Design 10 (1978) 350-355.
  * [5] G. M. Chaikin, An algorithm for high speed curve generation, Comput. Vis. Graph. Image Process. 3 (1974) 346–349.
  * [6] M. Charina, C. Conti, Polynomial reproduction of multivariate scalar subdivision schemes, J. Comput. Appl. Math., 240 (2013) 51–61.
  * [7] M. Charina, C. Conti, L. Romani, Reproduction of exponential polynomials by multivariate non-stationary subdivision schemes with a general dilation matrix, Numer. Math., 127(2) (2014) 223–254.
  * [8] E. Cohen, T. Lyche, R. Riesenfeld, Discrete B-splines and subdivision techniques in Computer-Aided Geometric Design and Computer Graphics, Comput. Graph. and Image Process 14 (1980) 87-111.
  * [9] C. Conti, N. Dyn, Convergence and smoothness of tensor-product of two non-uniform linear subdivision schemes, Comput. Aided Geom. Design 66 (2018) 16-18.
  * [10] C. Conti, K. Hormann, Polynomial reproduction for univariate subdivision schemes of any arity, J. Approx. Theory, 163 (2011) 413–437.
  * [11] C. Conti, L. Gemignani, L. Romani, From approximating to interpolatory non-stationary subdivision schemes with the same generation properties, Adv. Comput. Math., 35(2-4) (2011) 217–241.
  * [12] C. Conti, L. Gemignani, L. Romani, Exponential pseudo-splines: Looking beyond exponential B-splines, J. Math. Anal. Appl. 439(1) (2016) 32–56.
  * [13] C. Conti, L. Romani, Algebraic conditions on non-stationary subdivision symbols for exponential polynomial reproduction, J. Comput. Appl. Math. 236 (2011) 543–556.
  * [14] G. Deslauriers, S. Dubuc, Symmetric iterative interpolation, Constr. Approx. 5 (1989) 49–68.
  * [15] R. Donat, D. F. Yáñez, A nonlinear Chaikin-based binary subdivision scheme, J. Comput. Appl. Math. 349 (2019) 379-389.
  * [16] D. Doo, M. Sabin, Behaviour of recursive division surfaces near extraordinary points, Comput. Aided Des. 10(6) (1978) 356-360.
  * [17] N. Dyn, Subdivision Schemes in Computer-Aided Geometric Design, Advances in Numerical Analysis Vol. II: Wavelets, Subdivision Algorithms and Radial Basis Functions (W.A. Light ed.), Oxford University Press (1992), 36-104.
  * [18] N. Dyn, K. Hormann, M.A. Sabin, Z. Shen, Polynomial reproduction by symmetric subdivision schemes, J. Approx. Theory, 155 (2008) 28–42.
  * [19] N. Dyn, D. Levin, The subdivision experience, In Laurent, P., LeMéhauté, A. and Schumaker, L. (eds.): Curves and surfaces II, Wellesley, MA: A. K. Peters, 1991.
  * [20] N. Dyn, D. Levin, Analysis of asymptotically equivalent binary subdivision schemes, J. Math. Anal. Appl. 193 (1995) 594-621.
  * [21] N. Dyn, D. Levin, Subdivision schemes in geometric modelling, Acta Numerica 11, (2002), 73-144.
  * [22] N. Dyn, D. Levin, A. Luzzatto, Exponential reproducing subdivision schemes, Found. Comput. Math., 3 (2003) 187–206.
  * [23] N. Dyn, D. Levin, J. Yoon, A new method for the analysis of univariate nonuniform subdivision schemes, Constr. Approx. 40 (2014) 173-188.
  * [24] M.-e Fang, W. Ma, G. Wang, A generalized curve subdivision scheme of arbitrary order with a tension parameter, Comput. Aided Geom. Design, 27 (2010) 720-733.
  * [25] J. A. Gregory, R. Qu, Nonuniform corner cutting, Comput. Aided Geom. Design, 13 (1996) 763-772.
  * [26] M. K. Jena, P. Shunmugaraj, P. C. Das, A non-stationary subdivision scheme for curve interpolation Anziam J. 44(E) (2003) 216–235.
  * [27] B. Jeong, H. O. Kim, Y. J. Lee, J. Yoon, Exponential polynomial reproducing property of non-stationary symmetric subdivision schemes and normalized exponential B-splines, Adv. Comput. Math. 38 (2013) 647-666.
  * [28] B. Jeong, Y.J. Lee, J. Yoon, A family of non-stationary subdivision schemes reproducing exponential polynomials, J. Math. Anal. Appl. 402(1) (2013) 207–219.
  * [29] I. Khalidov and M. Unser From differential equations to the construction of wavelet-like bases, IEEE Tran. Sig. Proc., 54 (2005), 1256-1267.
  * [30] A. Levin, Polynomial generation and quasi-interpolation in stationary non-uniform subdivision, Comput. Aided Geom. Design, 20(1) (2003) 41–60.
  * [31] A. Ron, Exponential box splines, Constr. Approx., 4 (1988) 357-378.
  * [32] L. Romani, A Chaikin-based variant of Lane–Riesenfeld algorithm and its non-tensor product extension, Comput. Aided Geom. Design, 32 (2015) 22-49.
  * [33] Y. Tian, M. Pan, Corner-cutting subdivision surfaces of general degrees with parameters, J. Comput. Math. 38(5) (2020) 710-725.
  * [34] M. Unser and T. Blu Cardinal Exponential Splines : Part I -Theory and Filtering Algorithms, IEEE Tran. Sig. Proc., 53 (2005), 1425-1438.
  * [35] C. Vonesch, T. Blu and M. Unser Generalized Daubechies Wavelet Families, IEEE Tran. Sig. Proc., 55 (2007), 4415-4429.