Geometric Convergence Rates
for Cardinal Spline Subdivision
with General Integer Arity

Johan de Villiers$^{\ast \bullet }$ Mpfareleni Rejoyce Gavhi-Molefe$^\ast $

October 11, 2018. Accepted: April 23, 2019. Published online: October 10, 2019.

$^\ast $African Institute for Mathematical Sciences (AIMS), Cape Town, South Africa, e-mail: rejoyce@aims.ac.za.

$^\bullet $Department of Mathematical Sciences, Mathematics Division, Stellenbosch University, South Africa, e-mail: jmdv@sun.ac.za.
The financial assistance of the National Research Foundation (NRF), South Africa towards this research is hereby acknowledged. Also, we wish to express our appreciation to Xiaosheng Zhuang for valuable assistance with the code.

A rigorous convergence analysis is presented for arbitrary order cardinal spline subdivision with general integer arity, for which the binary case, with arity two, is a well-studied subject. Explicit geometric convergence rates are derived, and particular attention is devoted to the rendering of cardinal spline graphs and parametric curves.

MSC. Primary 65D07; 65D10; 65D17

Keywords. subdivision, arity, refinable functions, convergence rates, cardinal spline, parametric curves.

1 Introduction

Subdivision is an efficient tool for rendering graphs, and parametric curves or surfaces, and has a wide range of applications in computer graphics (see, e.g., [ 13 , 12 ] ). In particular binary subdivision, where the number of subdivision points are doubled at each iteration, is a well-studied subject (see, e.g., [ 18 , 11 , 7 , 8 ] ). In recent years, researchers have been investigating the more general concept of $d$-ary subdivision for any integer $d \geq 2$, which represents a $d$-fold increase in the number of subdivision points at each iteration, and with particular attention having been given to the arities $d=3$, or ternary subdivision, and $d=4$, or quaternary subdivision (see, e.g. [ 17 , 16 , 4 , 5 , 20 , 9 , 10 , 14 , 15 , 1 , 19 , 2 , 3 ] ).

Our primary focus in this paper is, as an extension of the binary subdivision results in [ 8 , ch. 3 ] , to establish a convergence analysis for $d$-ary cardinal spline subdivision, for any spline order $m \geq 2$, for the rendering of cardinal spline graphs and parametric curves. After first establishing, in Section 2, the $d$-refinement properties of the $m^{th}$ order centered cardinal B-spline $\phi _{m}$, we proceed in Section 3 to derive explicitly calculated geometric convergence rates of the corresponding $d$-ary subdivision scheme for bounded control point sequences. In the subsequent Sections 4 and 5, we present, by means also of graphical illustrations, the rendering of, respectively, the graphs of centered cardinal B-splines, and cardinal spline parametric curves in $\mathbb {R}^{s}$, for $s=2$ or $s=3$.

2 Centered Cardinal B-splines

For any positive integer $m$, the function $N_m : \mathbb {R}\rightarrow \mathbb {R}$ defined recursively by means of

\begin{equation} \label{Eq:2.1} N_1(x) \! : = \! \Big\{ \begin{smallmatrix} 1, & x \in [0,1); \\[1mm] 0, & x \in \mathbb {R}\backslash {[0,1)};\\ \end{smallmatrix} N_{m+1}(x) \! : =\! \! \displaystyle \int _0^1 \! N_{m}(x-t) dt,\ x\in \mathbb {R}, \ m =1,2, \ldots , \end{equation}

2.1

is called the cardinal B-spline of order $m$, as has been studied extensively since the appearance of original work by authors like Popoviciu [ 21 , 22 ] and Schoenberg [ 23 , 24 ] . The further integer-shift definition

\begin{equation} \label{Eq:2.2} \phi _{m}(x):= N_m\big(x+ \lfloor \tfrac {m}{2}\rfloor \big), \quad x \in \mathbb {R}, \end{equation}

2.2

with $\lfloor a\rfloor $ denoting the largest integer $\leq a$, then yields the function $\phi _m : \mathbb {R}\rightarrow \mathbb {R}$, which we shall call the centered cardinal B-spline of order $m$. Observe from 2.2 that $\phi _1 = N_1$, whereas $\phi _2$ is the linear hat function, that is,

\begin{equation} \label{Eq:2.3} \phi _2(x) := \Big\{ \begin{smallmatrix} 1-|x|, & x\in [-1,1); \\[1mm] 0, & x\in \mathbb {R}\backslash [-1,1). \end{smallmatrix} \end{equation}

2.3

For any non-negative integer $k$, we shall write $\pi _{k}$ for the space of polynomials with degree at most $k$, and the symbol $C^{k}(\mathbb {R})$ will denote the space of functions $f : \mathbb {R}\rightarrow \mathbb {R}$ such that, for $k\in \mathbb {N}$, the $k$-th order derivative $f^{(k)}$ is continuous on $\mathbb {R}$, whereas $C^{0}(\mathbb {R}) := C(\mathbb {R})$, the space of continuous real-valued function on $\mathbb {R}$. The symbol $C^{-1}(\mathbb {R})$ will denote the space of piecewise constant functions with respect to the integer partition $\mathbb {Z}$ of $\mathbb {R}$. We shall write $\ell (\mathbb {Z})$ for the space of all bi-infinite real-valued sequences $\{ c(k)\} = \{ c(k):k\in \mathbb {Z}\} $, and denote by $\ell _{0}(\mathbb {Z})$ the subspace of $\ell (\mathbb {Z})$ consisting of finitely supported sequences $\{ c(k)\} $ in $\ell (\mathbb {Z})$, that is, $ c(k)\ne 0$ for only a finite number of indices $k$. Also, we define $\sum \limits _k := \sum \limits _{k\in \mathbb {Z}}$.

As proved in [ 8 ] , the centered cardinal B-spline $\phi _m$ satisfies, for any $m\in \mathbb {N}$, the following properties:

$\phi _m$ is a compactly supported function, with support interval

\begin{equation} \label{Eq:2.4} {\rm supp} \ \phi _{m} = \big[-\lfloor \tfrac {m}{2}\rfloor , \lfloor \tfrac {m+1}{2}\rfloor \big]; \end{equation}
2.4
$\phi _m$ is a piecewise polynomial, with

\begin{equation} \label{Eq:2.5} \phi _{m}|_{[k,k+1)}\in \pi _{m-1}, \quad k\in \mathbb {Z}; \end{equation}
2.5
$\phi _m$ satisfies the smoothness condition

\begin{equation} \label{Eq:2.6} \phi _{m} \in C^{m-2}_{0}(\mathbb {R}); \end{equation}
2.6
$\phi _m$ has the positivity property

\begin{equation} \label{Eq:2.7} \phi _m(x) > 0, \quad x \in \big(-\lfloor \tfrac {m}{2}\rfloor , \lfloor \tfrac {m+1}{2}\rfloor \big); \end{equation}
2.7
the unit integral and partition of unity properties

\begin{equation} \label{Eq:2.8} \displaystyle \int _{-\infty }^{\infty } \phi _{m}(t) dt = \displaystyle \sum _k \phi _m (x-k) =1, \quad x \in \mathbb {R}; \end{equation}
2.8

hold, with, in particular, from the case $x=0$ in 2.8,

\begin{equation} \label{Eq:2.9} \displaystyle \sum _k \phi _m (k) =1; \end{equation}
2.9
the symmetry properties

\begin{align} \label{Eq:2.10} \phi _{m}(-x) = & \phi _{m}(x) \quad x \in \mathbb {R}, \quad {\rm if } \ m \ {\rm is} \ {\rm even}; \\ \label{Eq:2.11} \phi _{m}(1-x) = & \phi _{m}(x), \quad x \in \mathbb {R}, \quad {\rm if } \ m \ {\rm is} \ {\rm odd }, \quad m\geq 3, \end{align}

or, equivalently,

\begin{equation} \label{Eq:2.12} \phi _m \big( \tfrac {1}{2} + x\big) = \phi _m \big( \tfrac {1}{2} - x \big),\quad x \in \mathbb {R}, \quad {\rm if} \ \ m \ {\rm is} \ {\rm odd}, \quad m\geq 3, \end{equation}
2.12

are satisfied;
$\phi _m$ is a refinable function, with

\begin{equation} \label{Eq:2.13} \phi _{m}(x) = \displaystyle \sum _k p_{m}(k) \phi _{m} (2x-k), \quad x \in \mathbb {R}, \end{equation}
2.13

with refinement sequence given by

\begin{equation} \label{Eq:2.14} p_{m}(k) := \tfrac {1}{2^{m-1}} \textstyle {m \choose k+\lfloor \frac{m}{2}\rfloor }, \quad k \in \mathbb {Z}, \end{equation}
2.14

where ${j \choose \ell }:=0, \quad \ell \notin \{ 0,\ldots ,j\} $, and with the support of the sequence $\{ p_{m}(k)\} $ given by

\begin{equation} \label{Eq:2.15} {\rm supp} \ \{ p_{m}(k) \} = \big[-\lfloor \tfrac {m}{2}\rfloor , \lfloor \tfrac {m+1}{2}\rfloor \big]\cap \mathbb {Z}. \end{equation}
2.15

Observe in particular from 2.14 that the Laurent polynomial $P_{m}$ defined by

\begin{equation} \label{Eq:2.16} P_{m}(z) := \tfrac {1}{2}\displaystyle \sum _k p_{m}(k) z^{k}, \end{equation}

2.16

is given by

\begin{equation} \label{Eq:2.17} P_{m}(z) = z^{-\lfloor \frac{m}{2}\rfloor }\big(\tfrac {1+z}{2} \big)^{m}. \end{equation}

2.17

In our subdivision analysis of this paper, we shall rely on the fact that the refinement properties 2.13–2.17 of $\phi _m$ can be extended as follows.

Theorem 2.1

For any integers $m\in \mathbb {N}$ and $d \geq 2$, the centered cardinal B-spline $\phi _m$ in 2.2 is a $d$-refinable function, with

\begin{equation} \label{Eq:2.18} \phi _{m}(x) = \displaystyle \sum _k p_{m,d}(k) \phi _{m} (dx-k), \quad x \in \mathbb {R}, \end{equation}

2.18

where the refinement sequence $\{ p_{m,d}(k)\} \in \ell _{0}(\mathbb {Z})$ satisfies

\begin{equation} \label{Eq:2.19} \displaystyle \tfrac {1}{d}\sum _k p_{m,d}(k) z^{k} = P_{m,d}(z), \end{equation}

2.19

with $P_{m,d}$ denoting the Laurent polynomial defined by

\begin{equation} \label{Eq:2.20} P_{m,d}(z) := z^{-(d-1)\lfloor \frac{m}{2}\rfloor }\big(\tfrac {1+z+\cdots +z^{d-1}}{d} \big)^{m}, \end{equation}

2.20

and where the support of the sequence $\{ p_{m,d}(k)\} $ is given by

\begin{equation} \label{Eq:2.21} {\rm supp} \ \{ p_{m,d}(k)\} = \big[-(d-1)\lfloor \tfrac {m}{2}\rfloor , (d-1)\lfloor \tfrac {m+1}{2}\rfloor \big]\cap \mathbb {Z}. \end{equation}

2.21

Proof â–¼

First, observe from the first definition in 2.1 that the first-order B-spline $N_{1}$ is a refinable function, with

\begin{equation} \label{Eq:2.22} N_{1}(x) = \displaystyle \sum _k p(k) N_{1} (dx-k), \quad x \in \mathbb {R}, \end{equation}

2.22

where the refinement sequence $\{ p(k)\} \in \ell _{0}(\mathbb {Z})$ is given by

\begin{equation} \label{Eq:2.23} p(k) := \Big\{ \begin{smallmatrix} 1, & k=0,\ldots ,d-1; \\[1mm] 0, & k\in \mathbb {Z}\backslash \{ 0,\ldots ,d-1\} . \end{smallmatrix} \end{equation}

2.23

Also, the corresponding Laurent polynomial $P$ defined by

\begin{equation} \label{Eq:2.24} P(z) := \tfrac {1}{d}\displaystyle \sum _k p(k) z^{k}, \end{equation}

2.24

is then given by

\begin{equation} \label{Eq:2.25} P(z) = \tfrac {1+z+\cdots +z^{d-1}}{d}. \end{equation}

2.25

We proceed to prove inductively that, for any $m\in \mathbb {N}$, the cardinal B-spline $N_m$ is a refinable function, with

\begin{equation} \label{Eq:2.26} N_{m}(x) = \displaystyle \sum _k \tilde{p}_{m,d}(k) N_{m} (dx-k), \quad x \in \mathbb {R}, \end{equation}

2.26

where the refinement sequence $\{ \tilde{p}_{m,d}(k)\} \in \ell _{0}(\mathbb {Z})$ satisfies

\begin{equation} \label{Eq:2.27} \displaystyle \sum _k \tilde{p}_{m,d}(k) z^{k} = \tfrac {1}{d^{m-1}} \big(1+z+\cdots +z^{d-1}\big)^{m}. \end{equation}

2.27

After noting from 2.22, 2.24 and 2.25 that 2.26, 2.27 holds for $m=1$, we next suppose that 2.26, 2.27 is satisfied for a fixed integer $m\in \mathbb {N}$.

Now let the sequence $\{ p^{\ast }(k)\} \in \ell _{0}(\mathbb {Z})$ be defined by

\begin{equation} \label{Eq:2.28} \displaystyle \sum _k p^{\ast }(k) z^{k} := \tfrac {1}{d^{m}} \big(1+z+\cdots +z^{d-1}\big)^{m+1}. \end{equation}

2.28

It follows from 2.27 and 2.28 that

\begin{equation} \label{Eq:2.29} p^{\ast }(k) = \tfrac {1}{d} \sum _{j=0}^{d-1} \tilde{p}_{m,d}(k-j), \quad k\in \mathbb {Z}. \end{equation}

2.29

Now apply 2.1, 2.29 and 2.26 to deduce that, for any $x\in \mathbb {R}$,

\begin{align*} \displaystyle \sum _k p^{\ast }(k) N_{m+1} (dx-k) & =\tfrac {1}{d}\sum _k \Bigg\{ \sum _{j=0}^{d-1} \tilde{p}_{m,d}(k-j) \Bigg\} \displaystyle \int _0^1 N_{m} (dx-k-t) dt \\ & =\tfrac {1}{d}\sum _{j=0}^{d-1} \displaystyle \int _0^1 \left\{ \sum _k \tilde{p}_{m,d}(k-j) N_{m} (dx-t-k) \right\} dt \\ & = \tfrac {1}{d}\sum _{j=0}^{d-1} \displaystyle \int _0^1 \left\{ \sum _k \tilde{p}_{m,d}(k) N_{m} \left(d\big(x-\tfrac {t+j}{d}\big)-k\right) \right\} dt \\ & =\tfrac {1}{d}\sum _{j=0}^{d-1} \displaystyle \int _0^1 N_{m} \left(x-\tfrac {t+j}{d}\right) dt \\ & = \displaystyle \sum _{j=0}^{d-1} \displaystyle \int _{j/d}^{(j+1)/d} N_{m} \left(x-t\right) dt \\ & = \displaystyle \int _0^1 N_{m} \left(x-t\right) dt = N_{m+1}(x), \end{align*}

and thereby advancing the induction hypothesis from $m$ to $m+1$, which completes our inductive proof of 2.26, 2.27. Next, we observe from 2.19, 2.20 and 2.26, 2.27 that

\begin{equation} \label{Eq:2.30} p_{m,d}(k) = \tilde{p}_{m,d}\Big(k+(d-1)\lfloor \tfrac {m}{2}\rfloor \Big), \quad k\in \mathbb {Z}. \end{equation}

2.30

Hence we may now apply 2.30, 2.2 and 2.26 to deduce that, for any $x\in \mathbb {R}$,

\begin{align*} \displaystyle \sum _k p_{m,d}(k) \phi _{m} (dx-k) & = \displaystyle \sum _k \tilde{p}_{m,d}\big(k+(d-1)\lfloor \tfrac {m}{2}\rfloor \big)N_{m} \big(dx-k+\lfloor \tfrac {m}{2}\rfloor \big)\\ & = \displaystyle \sum _k \tilde{p}_{m,d}(k)N_{m} \big(d(x+\lfloor \tfrac {m}{2}\rfloor )-k\big) \\ & = N_{m} \big(x+\lfloor \tfrac {m}{2}\rfloor \big) = \phi _m(x), \end{align*}

which completes the proof of the refinability properties 2.18, 2.19, 2.20. Finally, note that the finite support property 2.21 is a direct consequence of 2.19, 2.20.

Proof â–¼

Remark 2.1

Observe that the special case $d=2$ of Theorem 2.1 corresponds precisely to the refinability properties 2.13–2.17 of $\phi _m$. â–¡

By applying 2.19 and 2.20 in Theorem 2.1, we deduce the following recursively formulation with respect to the index $m$ of the sequence $ \{ p_{m,d}(k):k\in \mathbb {Z}\} $.

Theorem 2.2

For any integers $m\in \mathbb {N}$ and $d \geq 2$, the refinement sequence $ \{ p_{m,d}(k)\} $ of Theorem 2.1 satisfies the recursive formulation

\begin{align} \label{Eq:2.31} p_{1,d}(k) = & \Big\{ \begin{smallmatrix} 1, \end{smallmatrix}& k=0,\ldots ,d-1; \\[1mm] 0, & k\in \mathbb {Z}\backslash \{ 0,\ldots ,d-1\} ; \end{align}

p_m+1,d(k) = 1d ∑_j=0^d-1 p_m,dk-j+(d-1)μ_m, kZ,

\end{align}

where

\begin{equation} \label{Eq:2.33} \mu _{m} := \Big\{ \begin{smallmatrix} 1, \quad if \ m \ is \ odd; \\[1mm] 0, \quad if \ m \ is \ even. \end{smallmatrix} \end{equation}

2.33

Theorem

Calculating by means of either 2.19, 2.20 or 2.31, 2.32, 2.33, we obtain the values in Tables 2.–2. of the sequence

\[ \big\{ p_{m,d}(k):k= -(d-1)\lfloor \tfrac {m}{2}\rfloor ,\ldots ,(d-1)\lfloor \tfrac {m+1}{2}\rfloor \big\} , \]

for $m=2, \ldots ,6$ and $d=2,3,4$.

$m$	$\{ p_{m,2}(k)\} $	$\{ p_{m,3}(k)\} $
2	$\begin{smallmatrix}\left\{ \frac{1}{2}\! , 1\! , \frac{1}{2}\right\} _{k=-1}^{1}\end{smallmatrix}$	$\begin{smallmatrix}\left\{ \frac{1}{3}\! ,\frac{2}{3}\! ,1\! ,\frac{2}{3}\! ,\frac{1}{3}\right\} _{k=-2}^{2}\end{smallmatrix}$
3	$\begin{smallmatrix}\left\{ \frac{1}{4}\! , \frac{3}{4}\! , \frac{3}{4}\! , \frac{1}{4}\right\} _{k=-1}^{2}\end{smallmatrix}$	$\begin{smallmatrix}\left\{ \frac{1}{9}\! ,\frac{3}{9}\! ,\frac{6}{9}\! ,\frac{7}{9}\! ,\frac{6}{9}\! ,\frac{3}{9}\! ,\frac{1}{9}\right\} _{k=-2}^{4}\end{smallmatrix}$
4	$\begin{smallmatrix}\left\{ \frac{1}{8}\! , \frac{4}{8}\! , \frac{6}{8}\! , \frac{4}{8}\! , \frac{1}{8}\right\} _{k=-2}^{2}\end{smallmatrix}$	$\begin{smallmatrix}\left\{ \frac{1}{27}\! ,\frac{4}{27}\! ,\frac{10}{27}\! ,\frac{16}{27}\! ,\frac{19}{27}\! ,\frac{16}{27}\! ,\frac{10}{27}\! ,\frac{4}{27}\! ,\frac{1}{27}\right\} _{k=-4}^{4}\end{smallmatrix}$
5	$\begin{smallmatrix}\left\{ \frac{1}{16}\! ,\frac{5}{16}\! ,\frac{10}{16}\! ,\frac{10}{16}\! ,\frac{5}{16}\! ,\frac{1}{16}\right\} _{k=-2}^{3}\end{smallmatrix}$	$\begin{smallmatrix} \left\{ \frac{1}{81}\! ,\frac{5}{81}\! ,\frac{15}{81}\! ,\frac{30}{81}\! ,\frac{45}{81}\! ,\frac{51}{81}\! ,\frac{45}{81}\! ,\frac{30}{81}\! ,\frac{15}{81}\! ,\frac{5}{81}\! ,\frac{1}{81}\right\} _{k=-4}^{6}\end{smallmatrix}$
6	$\begin{smallmatrix}\left\{ \frac{1}{32}\! ,\frac{6}{32}\! ,\frac{15}{32}\! ,\frac{20}{32}\! ,\frac{15}{32}\! ,\frac{6}{32}\! ,\frac{1}{32}\right\} _{k=-3}^{3}\end{smallmatrix}$	$ \begin{smallmatrix} \left\{ \frac{1}{243}\! ,\frac{6}{243}\! ,\frac{21}{243}\! ,\frac{50}{243}\! ,\frac{90}{243}\! ,\frac{126}{243}\! ,\frac{141}{243}\! ,\frac{126}{243}\! ,\frac{90}{243}\! ,\frac{50}{243}\! ,\frac{21}{243}\! ,\frac{6}{243}\! ,\frac{1}{243}\right\} _{k=-6}^{6} \end{smallmatrix} $

Table 2. The sequences $\big\{ p_{m,d}(k)\! :\! k=\! -(d\! -\! 1)\lfloor \tfrac {m}{2}\rfloor ,\ldots , (d\! -\! 1)\lfloor \tfrac {m+1}{2}\rfloor \big\} $, $d=2,3$.

$\{ p_{m,4}(k)\} $

$\begin{smallmatrix}m=2\end{smallmatrix}$

$ \begin{smallmatrix} \left\{ \frac{1}{4}\! ,\frac{2}{4}\! ,\frac{3}{4}\! ,1\! ,\frac{3}{4}\! ,\frac{2}{4}\! ,\frac{1}{4}\right\} _{k=-3}^{3} \end{smallmatrix} $

$\begin{smallmatrix}m=3\end{smallmatrix}$

$ \begin{smallmatrix} \left\{ \frac{1}{16}\! ,\frac{3}{16}\! ,\frac{6}{16}\! ,\frac{10}{16}\! ,\frac{12}{16}\! ,\frac{12}{16}\! ,\frac{10}{16}\! ,\frac{6}{16}\! ,\frac{3}{16}\! ,\frac{1}{16}\right\} _{k=-3}^{6} \end{smallmatrix} $

$\begin{smallmatrix}m=4\end{smallmatrix}$

$ \begin{smallmatrix} \left\{ \frac{1}{64}\! ,\frac{4}{64}\! ,\frac{10}{64}\! ,\frac{20}{64}\! ,\frac{31}{64}\! ,\frac{40}{64}\! ,\frac{44}{64}\! ,\frac{40}{64}\! ,\frac{31}{64}\! ,\frac{20}{64}\! ,\frac{10}{64}\! ,\frac{4}{64}\! ,\frac{1}{64}\right\} _{k=-6}^{6} \end{smallmatrix} $

$\begin{smallmatrix}m=5\end{smallmatrix}$

$ \begin{smallmatrix} \left\{ \frac{1}{256}\! ,\frac{5}{256}\! ,\frac{15}{256}\! ,\frac{35}{256}\! ,\frac{65}{256}\! ,\frac{101}{256}\! ,\frac{135}{256}\! ,\frac{155}{256}\! ,\frac{155}{256}\! ,\frac{135}{256}\! ,\frac{101}{256}\! ,\frac{65}{256}\! ,\frac{35}{256}\! ,\frac{15}{256}\! ,\frac{5}{256}\! ,\frac{1}{256}\right\} _{k=-6}^{9} \end{smallmatrix} $

$\begin{smallmatrix}m=6\end{smallmatrix}$

$ \begin{smallmatrix} \left\{ \frac{1}{1024}\! ,\frac{6}{1024}\! ,\frac{21}{1024}\! ,\frac{56}{1024}\! ,\frac{120}{1024}\! ,\frac{216}{1024}\! ,\frac{336}{1024}\! ,\frac{456}{1024}\! ,\frac{546}{1024}\! ,\frac{580}{1024}\! ,\frac{546}{1024}\! ,\frac{456}{1024}\! ,\frac{336}{1024}\! ,\frac{216}{1024}\! ,\frac{120}{1024}\! ,\frac{56}{1024}\! ,\frac{21}{1024}\! ,\frac{6}{1024}\! ,\frac{1}{1024}\right\} _{-9}^{9} \end{smallmatrix}\! \! \! $

Table 2. The sequences $\big\{ p_{m,d}(k)\! :\! k= -(d\! -\! 1)\lfloor \tfrac {m}{2}\rfloor ,\ldots , (d\! -\! 1)\lfloor \tfrac {m+1}{2}\rfloor \big\} $, $d=4$.

Finally in this section, by applying the recursive formulation 2.31–2.33 of Theorem 2.2, we prove the following sum-rule property of the sequence $ \{ p_{m,d}(k):k\in \mathbb {Z}\} $.

Theorem 2.3

For any integers $m\in \mathbb {N}$ and $d \geq 2$, the refinement sequence $ \{ p_{m,d}(k)\} $ of Theorem 2.1 satisfies the $d$-sum rule

\begin{equation} \label{Eq:2.34} \displaystyle \sum _k p_{m,d}(dk+\ell ) = 1, \quad \ell = 0,1, \ldots , d-1. \end{equation}

2.34

Proof â–¼

After noting from 2.31 that 2.34 holds for $m=1$, we next assume that 2.34 is true for some fixed $m\in \mathbb {N}$. It then follows from 2.32 that, for any $\ell \in \{ 0,1, \ldots , d-1\} $,

\begin{equation} \label{Eq:2.35} \sum _k p_{m+1,d}(dk+\ell ) = \tfrac {1}{d} \displaystyle \sum _{j=0}^{d-1}\sum _k p_{m,d}\big(dk+\ell -j+(d-1)\mu _{m}\big). \end{equation}

2.35

Let $\{ q,r\} $ denote the unique integer pair, with $r\in \{ 0,1, \ldots , d-1\} $, such that

\begin{equation} \label{Eq:2.36} \ell -j+(d-1)\mu _{m} = dq+r; \end{equation}

2.36

according to which then

\begin{equation} \label{Eq:2.37} \displaystyle \sum _k p_{m,d}(dk+\ell -j+(d-1)\mu _{m}) = \displaystyle \sum _k p_{m,d}\big(d(k+q)+r\big)= \displaystyle \sum _k p_{m,d}(dk+r) = 1, \end{equation}

2.37

from the inductive hypothesis. It then follows from 2.35 and 2.37 that

\[ \displaystyle \sum _k p_{m+1,d}(dk+\ell ) = 1, \]

which advances our inductive hypothesis from $m$ to $m+1$, and thereby completing our inductive proof of 2.34.

Proof â–¼

3 Geometrically Convergent Subdivision

In this section we develop a geometrically convergent subdivision scheme for the rendering, for any integer $m \geq 2$, of the graph of the cardinal spline $\Phi _{{\bf c},m}: \mathbb {R}\rightarrow \mathbb {R}$, as defined for any given bounded control point sequence ${\bf c} = \{ c(k):k\in \mathbb {Z}\} \in \ell (\mathbb {Z})$ by

\begin{equation} \label{Eq:3.1} \Phi _{{\bf c},m}(x) := \textstyle \sum \limits _k c(k) \phi _{m} (x-k), \quad x \in \mathbb {R}, \end{equation}

3.38

with $\phi _{m}$ denoting the $m$-th order centered cardinal B-spline, as given by 2.2. Our results extend trivially to the case where the control points are vectors in $\mathbb {R}^{s}$, for $s=2$ or $s=3$, in which case our convergent subdivision scheme renders the corresponding parametric cardinal spline curve in $\mathbb {R}^{s}$.

We shall use the symbol $\ell ^{\infty }(\mathbb {Z})$ to denote the subspace of bounded sequences ${\bf c} = \{ c(k)\} $ in $\ell (\mathbb {Z})$, that is,

\begin{equation} \label{Eq:3.2} \| {\bf c}\| _\infty = \| c(k)\| _\infty : = \textstyle \sup _{k}|c(k)| < \infty , \end{equation}

3.39

where $\sup _{k} := \sup _{k\in \mathbb {Z}}$. Note that $\ell _{0}(\mathbb {Z})\subset \ell ^{\infty }(\mathbb {Z})$.

Our convergence results below will be formulated in terms of the backwards difference operator $\Delta : \ell (\mathbb {Z}) \rightarrow \ell (\mathbb {Z})$, as defined by

\begin{equation} \label{Eq:3.3} (\Delta {\bf c})(k) : = c(k) - c(k-1), \quad k \in \mathbb {Z}, \quad {\bf c} = \{ c(k)\} \in \ell (\mathbb {Z}), \end{equation}

3.40

according to which

\begin{align} \label{Eq:3.4} (\Delta ^2 {\bf c})(k) :=& (\Delta (\Delta {\bf c}))(k) =c(k) - 2 \ c(k-1) +c(k-2), \quad k \in \mathbb {Z}, \\ \nonumber & {\bf c} = \{ c(k)\} \in \ell (\mathbb {Z}). \end{align}

Observe in particular that

\begin{equation} \label{Eq:3.5} {\bf c} \in \ell ^\infty (\mathbb {Z}) \Rightarrow \Delta {\bf c} \in \ell ^\infty (\mathbb {Z}), \quad {\rm with} \ \| \Delta {\bf c}\| _\infty \leq 2\| {\bf c}\| _\infty , \quad {\bf c} \in \ell ^\infty (\mathbb {Z}). \end{equation}

3.42

We shall rely on the following result from [ 8 ] , in which we adopt the empty-sum convention $\sum _{j=\sigma }^\tau a(j) : = 0$ if $\tau {\lt} \sigma $.

Lemma 3.1

For $k \in \mathbb {N}$, and any sequence ${\bf c} = \{ c(j)\} \in \ell (\mathbb {Z})$,

\begin{align} \label{Eq:3.6} & c(j+k) - 2 \ c(j) + c(j-k)= \\ \nonumber & = \displaystyle \sum _{\ell =1}^{k-1} \ell (\Delta ^2{\bf c})(j+k -\ell +1) + \displaystyle \sum _{\ell =1}^k \ell (\Delta ^2 {\bf c})(j-k+\ell +1), \quad j \in \mathbb {Z}. \end{align}

Proof â–¼

Let $k\in \mathbb {N}$, and apply 3.41 to deduce that, for any $j\in \mathbb {Z}$,

\begin{align} \nonumber & \displaystyle \sum _{\ell =1}^k \ell (\Delta ^2 {\bf c})(j-k+\ell +1)=\\ \nonumber & =\displaystyle \sum _{\ell =1}^k \ell \big\{ c(j-k+\ell +1) - 2c(j-k+\ell ) +c(j-k+\ell -1) \big\} \nonumber \\ & =\displaystyle \sum _{\ell =2}^{k+1} (\ell - 1) c(j-k+\ell ) -2 \displaystyle \sum _{\ell =1}^k \ell \ c(j-k+\ell ) + \displaystyle \sum _{\ell =0}^{k-1} (\ell +1) c(j-k+\ell ) \nonumber \\ & =\displaystyle \sum _{\ell =1}^k \big\{ \! (\ell \! -\! 1)\! -\! 2\ell \! +\! (\ell \! +\! 1) \! \big\} c(j\! -\! k\! +\! \ell )\! +\! k c (j\! +\! 1)\! +\! \big\{ c(j\! -\! k)\! -\! (k\! +\! 1)c(j)\big\} \nonumber \\ & =c(j-k) - c(j) + k \big\{ c(j+1) - c(j)\big\} , \label{Eq:3.7} \end{align}

and similarly, for $k\geq 2$,

\begin{align} \label{Eq:3.8} \nonumber & \displaystyle \sum _{\ell =1}^{k-1} \ell (\Delta ^2 {\bf c})(j+k-\ell +1)= \\ \nonumber & =\displaystyle \sum _{\ell =1}^{k-1} \ell \big\{ c(j+k-\ell +1) - 2c(j+k-\ell ) +c(j+k-\ell -1) \big\} \nonumber \\ & =\displaystyle \sum _{\ell =0}^{k-2} (\ell +1) c(j+k-\ell ) -2 \displaystyle \sum _{\ell =1}^{k-1} \ell \ c(j+k-\ell ) + \displaystyle \sum _{\ell =2}^{k} (\ell -1) c(j+k-\ell ) \nonumber \end{align}

\begin{align} & =\displaystyle \sum _{\ell =1}^{k-1} \! \! \big\{ (\ell \! +\! 1)\! -\! 2\ell \! +\! (\ell \! -\! 1) \big\} c(j\! +\! k\! -\! \ell )\! +\! \big\{ c(j\! +\! k)\! -\! kc(j\! +\! 1) \! \big\} \! +\! (k\! -\! 1)c(j)\nonumber \\ & =c(j+k) - c(j) + k \big\{ c(j) - c(j+1)\big\} . \end{align}

The desired result 3.43 is now a direct consequence of 3.43 and 3.44.

Proof â–¼

We shall also require the following properties of centered cardinal B-splines, as also derived in [ 8 ] , and in the proof of which we will rely on “Marsden’s identity" [ 6 ]

\begin{equation} \label{Eq:3.9} (x+t)^{m-1} = \displaystyle \sum _{k}g_{m}(k+t)N_{m}(x-k), \quad x, t \in \mathbb {R}, \end{equation}

3.44

where $g_{m}\in \pi _{m-1}$ is given by

\begin{equation} \label{Eq:3.10} g_{m}(x): = \textstyle \prod \limits _{j=1}^{m-1}(x+j), \quad x \in \mathbb {R}, \end{equation}

3.45

and with $N_{m}$ denoting the $m^{th}$ order cardinal B-spline.

Lemma 3.2

For any integer $m \geq 3$, the centered cardinal $B$-spline $\phi _{m}$, as defined by means of 2.3, satisfies

\begin{equation} \label{Eq:3.11} \displaystyle \sum _{k=1}^{m-1} k^2 \phi _{m}(k) = \tfrac {m}{24}, \quad if \ m \ is \ \ even, \ \ m\geq 4; \end{equation}

3.46

and

\begin{equation} \label{Eq:3.12} \displaystyle \sum _{k=1}^m \phi _{m} (k) = \tfrac {1}{2},\quad if \ m \ is \ odd. \end{equation}

3.47

Proof â–¼

First we differentiate the identity 3.44 repeatedly with respect to $t$, before setting $t=0$, to obtain the identities

\begin{equation} \label{Eq:3.13} x^\ell = \displaystyle \tfrac {\ell !}{(m-1)!} \displaystyle \sum _k g^{(m-1-\ell )}_m (k) N_m(x-k), \quad x\in \mathbb {R}, \quad \ell =0, 1, \ldots , m-1. \end{equation}

3.48

Now observe from 3.45 that

\begin{equation} \label{Eq:3.14} g_m(x) = x^{m-1} + \displaystyle \sum _{j=0}^{m-2} \alpha _{m}(j) x^j, \quad x\in \mathbb {R}, \end{equation}

3.49

where

\begin{equation} \label{Eq:3.15} \alpha _{m}(m-2) = 1+2+ \cdots + (m-1) = \displaystyle \tfrac {(m-1)m}{2}, \end{equation}

3.50

and

\begin{align} \label{Eq:3.16} \alpha _{m}(m\! -\! 3) & \! =\! 1 \big[2\! +\! \cdots \! +\! (m\! -\! 1) \big]\! +\! 2 \big[3\! +\! \cdots \! +\! (m\! -\! 1 )\big]\! +\! \cdots \! +\! (m\! -\! 2)(m\! -\! 1) \nonumber \\ & = \sum _{j=1}^{m-2} j \left[ \tfrac {(m-1)m}{2} - \tfrac {j(j+1)}{2} \right]\nonumber = \tfrac {(m-1)m}{2} \textstyle \sum \limits _{j=1}^{m-2} j - \tfrac {1}{2} \Big( \textstyle \sum \limits _{j=1}^{m-2}j^3 + \textstyle \sum \limits _{j=1}^{m-2} j^2 \Big) \nonumber \end{align}

\begin{align} & = \tfrac {1}{4} (m-2)(m-1)^2 m - \tfrac {1}{2} \Big[\tfrac {(m-2)^2(m-1)^2}{4} + \tfrac {(m-2)(m-1)(2m-3)}{6} \Big] \nonumber \\ & = \tfrac {m(m-1)(m-2)(3m-1)}{24}. \end{align}

It follows from 3.49, 3.50 and 3.51 that, for any $x \in \mathbb {R}$,

\begin{equation} \label{Eq:3.17} g^{(m-2)}_m(x) = (m-1)! x + (m-2)! \alpha _{m}(m-2) = (m-1)! x+ \tfrac {1}{2}m!; \end{equation}

3.51

and

\begin{align} \label{Eq:3.18} g^{(m-3)}_m(x) & = \displaystyle \tfrac {(m-1)!}{2}x^2+ (m-2)!\alpha _{m}(m-2) x + (m-3)! \alpha _{m}(m-3) \nonumber \\ & = \displaystyle \tfrac {(m-1)!}{2}x^2 + \tfrac {m!}{2} x+ \tfrac {m!(3m-1)}{24}. \end{align}

By using 3.51 and 3.52 in 3.48, we obtain the identities

\begin{align} \label{Eq:3.19} x = & \displaystyle \sum _k \left( k+ \tfrac {m}{2} \right) N_m (x-k), \quad x \in \mathbb {R}; \\ \label{Eq:3.20} x^2 = & \displaystyle \sum _k \left[ k^2+ m k+ \displaystyle \tfrac {m(3m-1)}{12}\right] N_m(x-k), \quad x \in \mathbb {R}. \end{align}

Since, moreover, as is evident form 2.2 and 2.9, we have

\begin{equation} \label{Eq:3.21} \displaystyle \sum _k N_m(k) = 1, \end{equation}

3.55

we may now set $x=0$ in 3.53 to deduce that

\begin{equation} \label{Eq:3.22} \displaystyle \sum _k k N_m(k) = \tfrac {m}{2}. \end{equation}

3.56

Similarly, we set $x=0$, in 3.54 to deduce by means also of 3.55 and 3.56 that

\[ 0 = \displaystyle \sum _k \! k^2 N_m (k) - m\left(\tfrac {m}{2}\right)+ \displaystyle \tfrac {m(3m-1)}{12}, \]

which yields

\begin{equation} \label{Eq:3.23} \displaystyle \sum _k k^2 N_m (k) = \displaystyle \tfrac {m(3m+1)}{12}. \end{equation}

3.57

By applying 2.2 , we now deduce from 3.55, 3.56 and 3.57 that, for any integer $n \geq 2$,

\begin{align*} \displaystyle \sum _k k^2 \phi _{2n} (k) = \! \displaystyle \sum _k k^2 N_{2n} (k\! +\! n) =\! \displaystyle \sum _k (k\! -\! n)^2 N_{2n} (k) =\displaystyle \tfrac {2n(6n+1)}{12} \! -\! 2n^2 \! +\! n^2 = \tfrac {n}{6}, \end{align*}

that is,

\begin{equation} \label{Eq:3.24} \displaystyle \sum _k k^2 \phi _{2n} (k) = \tfrac {n}{6}, \quad n=2,3,\dots . \end{equation}

3.58

According to the support property 2.4, as well as $\phi _{m}\in C(\mathbb {R})$, as follows from 2.6, we have, for all $n\in \mathbb {N}$,

\begin{align} \label{Eq:3.25} {\rm supp} \ \phi _{2n} = & [-n,n]\cap \mathbb {Z}, \quad { \rm with} \ \phi _{2n}(-n) = \phi _{2n}(n) = 0; \\ \label{Eq:3.26} {\rm supp} \ \phi _{2n+1} = & [-n,n+1]\cap \mathbb {Z}, \quad {\rm with} \ \phi _{2n+1}(-n) = \phi _{2n+1}(n+1) = 0. \end{align}

Now apply 3.58, 3.59, as well as the symmetry property 2.10, to deduce that, for $n\in \{ 2,3,\ldots \} $,

\begin{align} \tfrac {n}{6} =\displaystyle \sum _{k=-n+1}^{n-1} k^2 \phi _{2n} (k) = \displaystyle \sum _{k=-n+1}^{-1} k^2 \phi _{2n} (-k) + \displaystyle \sum _{k=1}^{n-1} k^2 \phi _{2n} (k) = 2\displaystyle \sum _{k=1}^{n-1} k^2 \phi _{2n} (k), \nonumber \end{align}

which yields the desired result 3.46.

Similarly, it follows from 2.9, together with the symmetry property 2.11, that, for $n\in \mathbb {N}$,

\begin{align} 1=\displaystyle \sum _{k} \phi _{2n+1} (k) =\displaystyle \sum _{k=-n+1}^{0} \phi _{2n+1} (1-k) + \displaystyle \sum _{k=1}^{n} \phi _{2n+1} (k) = 2\displaystyle \sum _{k=1}^{n} \phi _{2n+1} (k), \nonumber \end{align}

which implies 3.47, and thereby completing our proof.

Proof â–¼

For any integers $m \geq 2$ and $d \geq 2$, and a given control point sequence ${\bf c} = \{ c(k)\} \in \ell (\mathbb {Z})$, we now define the subdivision sequences $\big\{ {\bf c}^{[r]}_{m,d}\big\} \in \ell (\mathbb {Z})$, $r =0,1, \ldots $, recursively by means of the iterative scheme

\begin{equation} \label{Eq:3.27} {\bf c}^{[0]}_{m,d} : = {\bf c}; \quad {\bf c}^{[r+1]}_{m,d}: = {\mathcal S}_{m,d} {\bf c}^{[r]}_{m,d} = {\mathcal S}^r_{m,d} {\bf c}, \quad r=0,1, \ldots , \end{equation}

3.61

with ${\mathcal S}_{m,d}: \ell (\mathbb {Z}) \rightarrow \ell (\mathbb {Z})$ denoting the $m^{th}$ order cardinal spline subdivision operator given by

\begin{equation} \label{Eq:3.28} \big({\mathcal S}_{m,d}\ {\bf c}\big)(j) : = \displaystyle \sum _k p_{m,d}(j-dk) c(k), \quad j\in \mathbb {Z}, \quad {\bf c} = \{ c(k)\} \in \ell (\mathbb {Z}), \end{equation}

3.62

where $\{ p_{m,d}(k)\} \in \ell _{0}(\mathbb {Z}) $ is the refinement sequence of Theorem 2.1. We say that 3.61, 3.62 is a $d$-ary subdivision scheme, and we call $d$ the arity of the scheme. In particular, the values $d=2$, $d=3$ and $d=4$ yield, respectively, binary, ternary and quaternary subdivision schemes.

By applying Lemmas 3.1 and 3.2, we proceed to show that, if the control point sequence ${\bf c}$ is bounded, the difference between the values of the function $\Phi _{{\bf c},m}$ in 3.38 at the (dense in $\mathbb {R}$) $d$-adic point set $\displaystyle \big\{ \tfrac {j}{d^r}: j \in \mathbb {Z}, \ r =0,1, \ldots \big\} $ and the subdivision sequence values $\big\{ c^{[r]}_{m,d}(j):j \in \mathbb {Z}, \ r =0,1, \ldots \big\} $ is bounded as follows in terms of backward differences of the sequences ${\bf c}^{[r]}$.

Theorem 3.1

For any integer $m \geq 2$, and a given control point sequence ${\bf c} = \{ c(k) \} \in \ell ^{\infty } (\mathbb {Z})$, let the function $\Phi _{{\bf c},m}: \mathbb {R}\rightarrow \mathbb {R}$ be defined by 3.38 in terms of the $m^{th}$ order centered cardinal $B$-spline $\phi _{m}$, as given in 2.2. Then, for any integers $d \geq 2$ and $r\in \{ 0,1, \ldots \} $, the subdivision sequence ${\bf c}^{[r]}_{m,d}$, as defined recursively in 3.61, 3.62, satisfies

\begin{align} \label{Eq:3.29a} \Phi _{{\bf c},2} \big( \tfrac {j}{d^r}\big) - c^{[r]}_{2,d}(j) = & 0, \quad j \in \mathbb {Z}; \\ \label{Eq:3.29} \displaystyle \sup _j \big| \Phi _{{\bf c},m} \big( \tfrac {j}{d^r} \big) - c^{[r]}_{m,d}(j)\big| \leq & \left\{ \begin{array}{llll} (m-2) \big\| \Delta {\bf c}^{[r]}_{m,d}\big\| _\infty , & m \ \rm {odd}; \\[1mm] \displaystyle \tfrac {m}{24}\big\| \Delta ^2 {\bf c}^{[r]}_{m,d}\big\| _\infty , & m\ {\rm even}, \ m \geq 4.\end{array} \right. \end{align}

Proof â–¼

First, for any fixed $r\in \{ 0,1, \ldots \} $, we apply the refinability property 2.18 of $\phi _{m}$ to deduce from 3.38, together with 3.61, 3.62, that, for any $x\in \mathbb {R}$,

\begin{align*} \Phi _{{\bf c},m}(x) & = \displaystyle \sum _k c^{[0]}_{m,d}(k)\phi _{m} (x-k) \\ & =\displaystyle \sum _k c^{[0]}_{m,d}(k) \left\{ \displaystyle \sum _{\ell } p_{m,d}(\ell ) \phi _{m} (dx-dk-\ell ) \right\} \nonumber \\ & = \displaystyle \sum _k c^{[0]}_{m,d}(k) \left\{ \displaystyle \sum _{\ell } p_{m,d}(\ell -dk) \phi _{m} (dx-\ell ) \right\} \nonumber \\ & = \displaystyle \sum _{\ell }\left\{ \displaystyle \sum _k p_{m,d}(\ell -dk)c^{[0]}_{m,d}(k)\right\} \phi _{m} (dx-\ell )= \nonumber \\ & = \displaystyle \sum _{\ell }c^{[1]}_{m,d}(\ell )\phi _{m} (dx-\ell ) = \cdots = \displaystyle \sum _{\ell }c^{[r]}_{m,d}(\ell )\phi _{m} (d^{r}x-\ell ),\nonumber \end{align*}

that is,

\begin{equation} \label{Eq:3.30} \Phi _{{\bf c},m}(x) = \displaystyle \sum _{k}c^{[r]}_{m,d}(k)\phi _{m} (d^{r}x-k), \quad x\in \mathbb {R}, \end{equation}

3.61

and thus

\begin{equation} \label{Eq:3.31} \Phi _{{\bf c},m} \left( \tfrac {j}{d^r} \right) = \displaystyle \sum _{k}c^{[r]}_{m,d}(k)\phi _{m} (j-k) = \displaystyle \sum _{k}c^{[r]}_{m,d}(j-k)\phi _{m} (k), \quad j\in \mathbb {Z}. \end{equation}

3.62

By applying 2.9, we deduce from 3.62 that

\begin{equation} \label{Eq:3.32} \Phi _{{\bf c},m} \left( \tfrac {j}{d^r}\right) - c^{[r]}_{m,d}(j) = \displaystyle \sum _{k}\left\{ c^{[r]}_{m,d}(j-k) - c^{[r]}_{m,d}(j)\right\} \phi _{m} (k), \quad j \in \mathbb {Z}, \end{equation}

3.63

For $m=2$, we note from 2.3 that

\begin{equation} \label{Eq:3.33} \phi _{2} (k) = \delta (k), \quad k \in \mathbb {Z}, \end{equation}

3.64

with $\{ \delta (k)\} \in \ell _{0}(\mathbb {Z})$ denoting the Kronecker delta sequence defined by $\delta (0):=1$; $\delta (0) = 0, \ \ k \in \mathbb {Z}\backslash {\{ 0\} } $. The result 3.63 is now a direct consequence of 3.63 and 3.64.

Suppose next that $m=2n+1$ for some $n\in \mathbb {N}$. It then follows from 3.63 and 3.60, together with 3.40, as well as the fact that 2.4 and 2.7 imply

\begin{equation} \label{Eq:3.34} \phi _m(x) \geq 0, \quad x \in \mathbb {R}, \end{equation}

3.65

that, for any $j\in \mathbb {Z}$,

\begin{align} \nonumber \label{Eq:3.35} | \Phi _{{\bf c},2n+1} \left( \tfrac {j}{d^r}\right) - c^{[r]}_{2n+1,d}(j)| & = \Bigg|\sum _{k=-n+1}^{n}\left\{ c^{[r]}_{2n+1,d}(j-k) - c^{[r]}_{2n+1,d}(j)\right\} \phi _{2n+1} (k)\Bigg|\nonumber \end{align}

\begin{align} & =\Bigg|\displaystyle \sum _{k=1}^{n-1}\left\{ c^{[r]}_{2n+1,d}(j+k) - c^{[r]}_{2n+1,d}(j)\right\} \phi _{2n+1} (-k) \nonumber \\ & \quad -\displaystyle \sum _{k=1}^{n}\left\{ c^{[r]}_{2n+1,d}(j) - c^{[r]}_{2n+1,d}(j-k)\right\} \phi _{2n+1} (k) \Bigg| \nonumber \\ & =\Bigg| \displaystyle \sum _{k=1}^{n-1} \left\{ \sum _{\ell = j+1}^{j+k}(\Delta {\bf c}^{[r]}_{2n+1,d})(\ell )\right\} \phi _{2n+1} (-k) \nonumber \\ & \quad - \displaystyle \sum _{k=1}^{n}\left\{ \sum _{\ell = j-k+1}^{j}(\Delta {\bf c}^{[r]}_{2n+1,d})(\ell )\right\} \phi _{2n+1} (k) \Bigg|\nonumber \\ & \leq \| \Delta {\bf c}^{[r]}_{2n+1,d} \| _\infty \left\{ \displaystyle \sum _{k=1}^{n-1} k \phi _{2n+1} (\! -\! k)\! +\! \displaystyle \sum _{k=1}^{n} k \phi _{2n+1} (k)\right\} \end{align}

Now observe from the symmetry property 2.11 that

\begin{align*} \displaystyle \sum _{k=1}^{n-1} k \phi _{2n+1} (-k) & =\! \displaystyle \sum _{k=1}^{n-1} k \phi _{2n+1} (1\! +\! k) =\! \displaystyle \sum _{k=2}^{n} (k\! -\! 1) \phi _{2n+1} (k) = \! \displaystyle \sum _{k=1}^{n} (k\! -\! 1) \phi _{2n+1} (k), \end{align*}

which, together with 3.66, as well as 3.47 in Lemma 3.2, yields

\begin{align*} |\Phi _{{\bf c},2n+1} \big( \tfrac {j}{d^r}\big) - c^{[r]}_{2n+1,d}(j)| & \leq \| \Delta {\bf c}^{[r]}_{2n+1,d} \| _\infty \displaystyle \sum _{k=1}^{n} (2k-1) \phi _{2n+1} (k) \\ & \leq (2n-1)\| \Delta {\bf c}^{[r]}_{2n+1,d} \| _\infty \displaystyle \sum _{k=1}^{n}\phi _{2n+1} (k)\\ & =\big(n-\tfrac {1}{2}\big)\| \Delta {\bf c}^{[r]}_{2n+1,d} \| _\infty , \end{align*}

and thereby implying the first line of 3.64.

Suppose next that $m=2n$ for some integer $n\geq 2$. It then follows from 3.63 and 3.59, together with the symmetry property 2.10, that, for any $j\in \mathbb {Z}$,

\begin{align} \nonumber \label{Eq:3.36} & \Phi _{{\bf c},2n} \big( \tfrac {j}{d^r}\big) - c^{[r]}_{2n,d}(j)= \\ \nonumber & = \displaystyle \sum _{k=-n+1}^{n-1}\left\{ c^{[r]}_{2n,d}(j-k) - c^{[r]}_{2n,d}(j)\right\} \phi _{2n} (k)\nonumber \\ & =\displaystyle \sum _{k=1}^{n-1}\! \left\{ c^{[r]}_{2n,d}(j\! +\! k)\! -\! c^{[r]}_{2n,d}(j)\right\} \phi _{2n} (\! -\! k) \! -\! \displaystyle \sum _{k=1}^{n-1}\! \left\{ c^{[r]}_{2n,d}(j) - c^{[r]}_{2n,d}(j-k)\right\} \phi _{2n} (k) \nonumber \\ & =\displaystyle \sum _{k=1}^{n-1}\left\{ c^{[r]}_{2n,d}(j+k) - 2c^{[r]}_{2n,d}(j) + c^{[r]}_{2n,d}(j-k)\right\} \phi _{2n} (k). \end{align}

Hence we may now apply 3.43 in Lemma 3.1 to deduce from 3.66 that

\begin{align*} & \Phi _{{\bf c},2n} \big( \tfrac {j}{d^r}\big) - c^{[r]}_{2n,d}(j)= \\ & = \displaystyle \sum _{k=1}^{n-1} \left\{ \sum _{\ell = 1}^{k-1}\ell \triangle ^{2} {\bf c}^{[r]}_{2n,d}(j+k-\ell +1)+ \sum _{\ell = 1}^{k}\ell \triangle ^{2} {\bf c}^{[r]}_{2n,d}(j-k+\ell +1)\right\} \phi _{2n} (k), \end{align*}

and thus, by using also 3.65,

\begin{align} | \Phi _{{\bf c},2n} \big( \tfrac {j}{d^r}\big) - c^{[r]}_{2n,d}(j)| & \leq \| \triangle ^{2} {\bf c}^{[r]}_{2n,d}\| _\infty \displaystyle \sum _{k=1}^{n-1} \left\{ \sum _{\ell = 1}^{k-1}\ell + \sum _{\ell = 1}^{k}\ell \right\} \phi _{2n} (k) \nonumber \\ & = \| \triangle ^{2} {\bf c}^{[r]}_{2n,d}\| _\infty \sum _{\ell = 1}^{k-1} \left\{ \tfrac {(k-1)k}{2} + \tfrac {k(k+1)}{2} \right\} \phi _{2n} (k) \nonumber \\ & = \| \triangle ^{2} {\bf c}^{[r]}_{2n,d}\| _\infty \displaystyle \sum _{k=1}^{n-1} k^{2}\phi _{2n} (k) = \tfrac {n}{12} \| \triangle ^{2} {\bf c}^{[r]}_{2n,d}\| _\infty , \nonumber \end{align}

by virtue of 3.46 in Lemma 3.2, and thereby yielding the second line of 3.64.

Proof â–¼

We proceed to prove that the sequences $\big\{ \big\| \triangle {\bf c}^{[r]}_{m,d}\big\| _\infty : r=0,1,\ldots \big\} $ and $\big\{ \| \triangle ^2 {\bf c}^{[r]}_{m,d}\| _\infty : r=0,1,\ldots \big\} $, as appearing in the upper bounds 3.64, converge geometrically to zero for $r\rightarrow \infty $, as follows.

Theorem 3.2

In Theorem 3.1, for any integer $m\geq 3$, the geometric convergence rates

\begin{align} \label{Eq:3.37} \big\| \triangle {\bf c}^{[r]}_{m,d}\big\| _\infty \leq & \| \triangle {\bf c}\| _\infty \big(\tfrac {1}{d} \big)^r, \quad r=0,1,\ldots ; \\ \label{Eq:3.38} \big\| \triangle ^{2} {\bf c}^{[r]}_{m,d}\big\| _\infty \leq & \| \triangle ^{2} {\bf c}\| _\infty \big(\tfrac {1}{d^2} \big)^r, \quad r=0,1,\ldots , \end{align}

are satisfied.

Proof â–¼

For any integer $r\in \mathbb {N}$, we may apply 3.61, 3.62, together with 3.40, as well as the recursive formula 2.32 in Theorem 2.2, to obtain, for any $j\in \mathbb {Z}$,

\begin{align*} \Big(\triangle {\bf c}^{[r]}_{m,d}\Big)(j) & = {\bf c}^{[r]}_{m,d}(j) - {\bf c}^{[r]}_{m,d}(j-1)\nonumber \\ & = \displaystyle \sum _k \big\{ p_{m,d}(j-dk) - p_{m,d}(j-1-dk)\big\} c^{[r-1]}_{m,d}(k)\nonumber \\ & = \tfrac {1}{d}\displaystyle \sum _k \sum _{\ell =0}^{d-1}\big\{ p_{m-1,d}\big(j-dk+(d-1)\mu _{m-1} - \ell \big) - \\ \nonumber & \quad -p_{m-1,d}\big(j-dk+(d-1)\mu _{m-1} -1- \ell \big)\big\} c^{[r-1]}_{m,d}(k)\\ \nonumber & = \tfrac {1}{d}\displaystyle \sum _k \Big\{ p_{m-1,d}\big(j-dk+(d-1)\mu _{m-1}\big) \end{align*}

\begin{align*} \nonumber & \quad - p_{m-1,d}\big(j-d(k+1)+(d-1)\mu _{m-1}\big)\Big\} c^{[r-1]}_{m,d}(k)\nonumber \\ & =\tfrac {1}{d}\Big\{ \displaystyle \sum _k p_{m-1,d}\big(j+(d-1)\mu _{m-1}-dk\big)c^{[r-1]}_{m,d}(k)\\ \nonumber & \quad -\displaystyle \sum _k p_{m-1,d}\big(j+(d-1)\mu _{m-1}-dk\big)c^{[r-1]}_{m,d}(k-1)\Big\} \nonumber \\ & = \tfrac {1}{d}\displaystyle \sum _k p_{m-1,d}\big(j+(d-1)\mu _{m-1}-dk\big)\Big(\triangle {\bf c}^{[r-1]}_{m,d}\Big)(k),\nonumber \end{align*}

that is,

\begin{equation} \label{Eq:3.39} \Big(\triangle {\bf c}^{[r]}_{m,d}\Big)(j) = \tfrac {1}{d}\displaystyle \sum _k p_{m-1,d}\big(j+(d-1)\mu _{m-1}-dk\big)\Big(\triangle {\bf c}^{[r-1]}_{m,d}\Big)(k), \quad j\in \mathbb {Z}. \end{equation}

3.59

By using 3.59 and 3.41, a similar argument to the one used to derive 3.59

then yields

\begin{align} \label{Eq:3.40} & \Big(\triangle ^2 {\bf c}^{[r]}_{m,d}\Big)(j)= \\ \nonumber & =\tfrac {1}{d^2}\displaystyle \sum _k p_{m-2,d}\big(j\! +\! (d\! -\! 1)(\mu _{m-1} \! +\! \mu _{m-2})\! -\! dk\big)\Big(\triangle ^{2} {\bf c}^{[r-1]}_{m,d}\Big)(k), \quad j\in \mathbb {Z}. \end{align}

Since, moreover, 2.33 implies $\mu _{m-1} +\mu _{m-2} = 1$, it follows from 3.60 that

\begin{equation} \label{Eq:3.41} \Big(\triangle ^2 {\bf c}^{[r]}_{m,d}\Big)(j) = \tfrac {1}{d^2}\displaystyle \sum _k p_{m-2,d}\big(j+d-1-dk\big)\Big(\triangle ^{2} {\bf c}^{[r-1]}_{m,d}\Big)(k), \quad j\in \mathbb {Z}. \end{equation}

3.61

According to 2.19, 2.20, we have

\begin{equation} \label{Eq:3.42} p_{m,d}(k)\geq 0, \quad , k\in \mathbb {Z}. \end{equation}

3.62

By applying 3.59, 3.61 and 3.62, we obtain the bounds

\begin{align*} |\big(\triangle {\bf c}^{[r]}_{m,d}\big)(j)| \leq & \big\| \triangle {\bf c}^{[r-1]}_{m,d}\big\| _\infty \tfrac {1}{d}\displaystyle \sum _k p_{m-1,d}\big(j+(d-1)\mu _{m}-dk\big), \ j\in \mathbb {Z}, \\[1mm] |\big(\triangle ^2 {\bf c}^{[r]}_{m,d}\big)(j)| \leq & \big\| \triangle ^{2} {\bf c}^{[r-1]}_{m,d}\big\| _\infty \tfrac {1}{d^2}\displaystyle \sum _k p_{m-2,d}\big(j+d-1-dk\big), j\in \mathbb {Z}, \end{align*}

and thus, from the $d$-sum rule 2.34 in Theorem 2.3,

\begin{align*} |\big(\triangle {\bf c}^{[r]}_{m,d}\big)(j)| \leq \tfrac {1}{d}\| \triangle {\bf c}^{[r-1]}_{m,d}\| _\infty ;\ j\in \mathbb {Z}, \\[1mm] |\big(\triangle ^2 {\bf c}^{[r]}_{m,d}\big)(j)| \leq \tfrac {1}{d^2}\| \triangle ^{2} {\bf c}^{[r-1]}_{m,d}\| _\infty , j\in \mathbb {Z}, \end{align*}

from which we deduce that

\begin{align} \label{Eq:3.43} \| \big(\triangle {\bf c}^{[r]}_{m,d}\big)\| _\infty \leq & \tfrac {1}{d}\| \triangle {\bf c}^{[r-1]}_{m,d}\| _\infty , \quad r=1,2,\ldots ; \\ \label{Eq:3.44} \| \big(\triangle ^2 {\bf c}^{[r]}_{m,d}\big)\| _\infty \leq & \tfrac {1}{d^2}\big\| \triangle ^{2} {\bf c}^{[r-1]}_{m,d}\big\| _\infty , \quad r=1,2,\ldots . \end{align}

For any $r\in \mathbb {N}$, we now apply 3.63 repeatedly to obtain

\[ \| \triangle {\bf c}^{[r]}_{m,d}\| _\infty \leq \tfrac {1}{d}\left( \tfrac {1}{d}\| \triangle {\bf c}^{[r-2]}_{m,d}\| _\infty \right) \leq \cdots \leq \big( \tfrac {1}{d}\big)^r\| \triangle {\bf c}^{[0]}_{m,d}\| _\infty , \]

which, together with 3.61, proves 3.66.

Similarly, repeated application of 3.64 yields the desired result 3.67. Finally, note that 3.66 and 3.67 trivially holds for $r=0$.

Proof â–¼

We may now combine the results of Theorems 3.1 and 3.2 to obtain the following subdivision convergence result.

Corollary 3.1

For any integers $m \geq 2$ and $d\geq 2$, the $d$-ary $m^{th}$ order cardinal spline subdivision operator ${\mathcal S}_{m,d}: \ell (\mathbb {Z}) \rightarrow \ell (\mathbb {Z})$, as defined by 3.62 in terms of the refinement sequence $\{ p_{m,d}(k)\} \in \ell _{0}(\mathbb {Z})$ of Theorem 2.1, provides, for any given control point sequence ${\bf c} = \{ c(k) \} \in \ell ^{\infty }(\mathbb {Z})$, a convergent subdivision scheme 3.61, where the recursively generated subdivision sequences ${\bf c}^{[r]}_{m,d}=\{ c^{[r]}_{m,d}(k) \} \in \ell ^{\infty }(\mathbb {Z})$, $r=0,1,\ldots $, satisfy

\begin{eqnarray} \label{Eq:3.45} \Phi _{{\bf c},2} \big( \tfrac {j}{d^r}\big) - c^{[r]}_{2,d}(j) = 0, \quad j \in \mathbb {Z}, \end{eqnarray}

and, for $m \geq 3$, the geometric convergence rates

\begin{equation} \label{Eq:3.46} \displaystyle \sup _j \Big| \Phi _{{\bf c},m} \big( \tfrac {j}{d^r} \big) - c^{[r]}_{m,d}(j) \Big| \leq \left\{ \begin{array}{llll} \displaystyle \tfrac {m-2}{2} \| \triangle {\bf c}^{[r]}_{m,d} \| _\infty \big(\tfrac {1}{d} \big)^r, & \! m \ {\rm odd}; \\[2mm] \displaystyle \tfrac {m}{24}\| \triangle ^2 {\bf c}^{[r]}_{m,d}\| _\infty \big(\tfrac {1}{d^2} \big)^r, & \! m \ {\rm even}, \ m\geq 4; \end{array} \right. \! r=0,1,\ldots \end{equation}

3.66

with $\Phi _{{\bf c},m}: \mathbb {R}\rightarrow \mathbb {R}$ denoting the cardinal spline given by 3.38.

Remark 3.1

(a) For $m=2$, it follows from 3.38 and 3.64 that $\Phi _{{\bf c},2}$ is the (continuous) piecewise linear interpolant such that

\begin{equation} \label{Eq:3.47} \Phi _{{\bf c},2}(j) = c(j), \quad j\in \mathbb {Z}. \end{equation}

3.67

Since also the $d$-adic point set $\displaystyle \big\{ \tfrac {j}{d^r}: j \in \mathbb {Z}, \ r =0,1, \ldots \big\} $ is dense in $\mathbb {R}$, it follows from 3.65 that the subdivision sequences $ c^{[r]}_{2,d},\ \ r=0,1,\ldots $, “fill up" the graph of linear cardinal spline $\Phi _{{\bf c},2}$.

(b) For $m \geq 3$ and any fixed $x\in \mathbb {R}$, let the sequence $\{ j_r:r=0,1,\ldots \} \subset \mathbb {Z}$ be such that

\begin{equation} \label{Eq:3.48} \tfrac {j_r}{d^r} \rightarrow x, \quad r\rightarrow \infty . \end{equation}

3.68

Since, from 3.38 and 2.6, the function $\Phi _{{\bf c},m}$ is continuous at $x$, it then follows from 3.66 and 3.68 that

\begin{equation} \label{Eq:3.49} c^{[r]}_{m,d}(j_r)\rightarrow \Phi _{{\bf c},m}(x), \quad r\rightarrow \infty , \end{equation}

3.69

according to which the co-ordinate sequences $\displaystyle \big\{ \big( \tfrac {j}{d^r}, c^{[r]}_{m,d}(j)\big):j\in \mathbb {Z}\big\} $, $r=0,1,\ldots $, do indeed converge to the graph of the cardinal spline $\Phi _{{\bf c},m}$ as $r\rightarrow \infty $.

${\bf c} \in \ell (\mathbb {Z})$, if $m=2$;
$\Delta {\bf c} \in \ell ^{\infty }(\mathbb {Z})$, if $m$ is odd;
$\Delta ^2 {\bf c} \in \ell ^{\infty }(\mathbb {Z})$, if $m$ is even, with $m\geq 4$.

(d) By applying 3.42, it follows from 3.66 in Corollary 3.1 that, for $m\geq 3$,

\begin{equation} \label{Eq:3.50} \displaystyle \sup _j | \Phi _{{\bf c},m} \big( \tfrac {j}{d^r} \big) - c^{[r]}_{m,d}(j) | \leq \left\{ \begin{array}{llll} \displaystyle (m-2) \| {\bf c}\| _\infty \big(\tfrac {1}{d} \big)^r, & {\rm if} \ \ m \ \ {\rm is \ \ odd}; \\[2mm] \frac{m\| {\bf c}\| _\infty }{6}\big(\tfrac {1}{d^2} \big)^r, & {\rm if} \ \ m \ \ {\rm is \ \ even}, \end{array} \right. r=0,1,\ldots \end{equation}

3.70

Next, we observe from the definition 3.62 of the $d$-ary cardinal spline subdivision operator ${\mathcal S}_{m,d}: \ell (\mathbb {Z}) \rightarrow \ell (\mathbb {Z})$ that, for any sequence ${\bf c} = \{ c(k)\} \in \ell (\mathbb {Z})$ and integers $j\in \mathbb {Z}$, $\ell \in \{ 0,\ldots , d-1\} $,

\[ \big({\mathcal S}_{m,d} \ {\bf c}\big)(dj+\ell ) = \displaystyle \sum _k p_{m,d}\big(d(j-k)+\ell \big)c(k) = \displaystyle \sum _k p_{m,d}\big(dk+\ell \big)c(j-k), \]

and thus

\begin{align} \label{Eq:4.1} & \big({\mathcal S}_{m,d}\ {\bf c}\big)(dj+\ell ) = \displaystyle \sum _k w^{[\ell ]}_{m,d}(k)c(j-k), \end{align}

$j\in \mathbb {Z}; \ell =0,\ldots ,d-1; {\bf c} = \{ c(k)\} \in \ell (\mathbb {Z})$, with $\{ w^{[\ell ]}_{m,d}(k) \} \in \ell _{0}(\mathbb {Z})$ denoting the weight sequences defined by

\begin{equation} \label{Eq:4.2} w^{[\ell ]}_{m,d}(k) := p_{m,d}\big(dk+\ell \big), \quad k\in \mathbb {Z}; \quad \ell =0,\ldots ,d-1. \end{equation}

3.72

It follows from 3.71 that the subdivision scheme 3.61, 3.62 may be alternatively formulated, for any given control point sequence ${\bf c} = \{ c(k)\} \in \ell (\mathbb {Z})$, by

\begin{align} \label{Eq:4.3} & {\bf c}^{[0]}_{m,d} : ={\bf c};\\ \nonumber & {\bf c}^{[r+1]}_{m,d}\big(dj+\ell \big) = \displaystyle \sum _k w^{[\ell ]}_{m,d}(k){\bf c}^{[r]}_{m,d}(j-k), \ j\in \mathbb {Z}; \ \ell =0,\ldots ,d-1; \ r=0,1,\ldots ; \end{align}

where the weight sequences $\{ w^{[\ell ]}_{m,d}(k) \} \in \ell _{0}(\mathbb {Z})$, $\ell = 0,\ldots ,d-1$, are given by 3.72. Observe from 3.72 and 2.21 that the weight sequences $\{ w^{[\ell ]}_{m,d}(k) \} \in \ell _{0}(\mathbb {Z})$ has support

\begin{align} \label{Eq:4.4} & {\rm supp} \ \big\{ w^{[\ell ]}_{m,d}(k) \big\} =\Big[-\lfloor \tfrac {(d-1)\lfloor \frac{m}{2}\rfloor + \ell }d\rfloor ,\lfloor \tfrac {(d-1)\lfloor \frac{m+1}{2}\rfloor - \ell }d\rfloor \Big]\cap \mathbb {Z}, \quad \ell =0,\ldots ,d-1. \end{align}

By using 3.72, together with Tables 2. and 2., we obtain the $d$-ary subdivision weight sequences

\begin{align*} & \Big\{ w^{[\ell ]}_{m,d}(k):k = \lceil \tfrac {-(d-1)\lfloor \frac{m}{2}\rfloor - \ell }d\rceil , \ldots , \lfloor \tfrac {(d-1)\lfloor \frac{m+1}{2}\rfloor - \ell }d\rfloor \Big\} , \end{align*}

$\ell =0,\ldots ,d-1,$ in Tables 3.–3., for $m=2,\ldots ,6$ and $d=2,3,4$.

$m$	$\ell =0$	$\ell =1$
2	$ \begin{smallmatrix} \{ 1\} _{k=0} \end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{1}{2}, \frac{1}{2}\right\} _{k=-1}^{0} \end{smallmatrix}$
3	$ \begin{smallmatrix}\left\{ \frac{3}{4}, \frac{1}{4}\right\} _{k=0}^{1}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{1}{4}, \frac{3}{4}\right\} _{k=-1}^{0}\end{smallmatrix}$
4	$ \begin{smallmatrix}\left\{ \frac{1}{8}, \frac{6}{8}, \frac{1}{8}\right\} _{k=-1}^{1}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{4}{8},\frac{4}{8}\right\} _{k=-1}^{0}\end{smallmatrix}$
5	$ \begin{smallmatrix}\left\{ \frac{1}{16}, \frac{10}{16}, \frac{5}{16}\right\} _{k=-1}^{1}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{5}{16}, \frac{10}{16}, \frac{1}{16}\right\} _{k=-1}^{1}\end{smallmatrix}$
6	$ \begin{smallmatrix}\left\{ \frac{6}{32}, \frac{20}{32}, \frac{6}{32}\right\} _{k=-1}^{1}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{1}{32}, \frac{15}{32}, \frac{15}{32},\frac{1}{32}\right\} _{k=-2}^{1}\end{smallmatrix}$

Table 3. The weight sequences $\{ w^{[\ell ]}_{m,2}(k)\} $.

$m$

$ \begin{smallmatrix} \ell =0 , \quad \end{smallmatrix}$

ℓ=1,

ℓ=2


2 $ \begin{smallmatrix} \{ 1\} _{k=0} & \left\{ \frac{1}{3}, \frac{2}{3}\right\} _{k=-1}^{0} & \left\{ \frac{2}{3}, \frac{1}{3}\right\} _{k=-1}^{0} \end{smallmatrix} $
3 $ \begin{smallmatrix} \left\{ \frac{6}{9}, \frac{3}{9}\right\} _{k=0}^{1} & \left\{ \frac{1}{9}, \frac{7}{9},\frac{1}{9}\right\} _{k=-1}^{1} & \left\{ \frac{3}{9}, \frac{6}{9}\right\} _{k=-1}^{0} \end{smallmatrix} $
4 $ \begin{smallmatrix} \left\{ \frac{4}{27}, \frac{19}{27}, \frac{4}{27}\right\} _{k=-1}^{1} & \left\{ \frac{10}{27},\frac{16}{27},\frac{1}{27}\right\} _{k=-1}^{1} & \left\{ \frac{1}{27}, \frac{16}{27}, \frac{10}{27}\right\} _{k=-2}^{0} \end{smallmatrix} $
5 $ \begin{smallmatrix} \left\{ \frac{5}{81}, \frac{45}{81}, \frac{30}{81},\frac{1}{81}\right\} _{k=-1}^{2} & \left\{ \frac{15}{81}, \frac{51}{81}, \frac{15}{81}\right\} _{k=-1}^{1} & \left\{ \frac{1}{81}, \frac{30}{81}, \frac{45}{81}, \frac{5}{81}\right\} _{k=-1}^{0} \end{smallmatrix} $
6 $ \begin{smallmatrix} \left\{ \frac{1}{243}, \frac{50}{243}, \frac{141}{243},\frac{50}{243}, \frac{1}{243}\right\} _{k=-2}^{2} & \left\{ \frac{6}{243}, \frac{90}{243}, \frac{126}{243}, \frac{21}{243}\right\} _{k=-2}^{1} & \left\{ \frac{21}{243}, \frac{126}{243}, \frac{90}{243}, \frac{6}{243}\right\} _{k=-2}^{1} \end{smallmatrix} $

None

The weight sequences $\{ w^{[\ell ]}_{m,3}(k)\} $.

$m$	$\ell =0$	$\ell =1$
2	$ \begin{smallmatrix}\{ 1\} _{k=0}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{1}{4}, \frac{3}{4}\right\} _{k=-1}^{0}\end{smallmatrix}$
3	$ \begin{smallmatrix}\left\{ \frac{10}{16}, \frac{6}{16}\right\} _{k=0}^{1}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{1}{16}, \frac{12}{16}, \frac{3}{16}\right\} _{k=-1}^{1}\end{smallmatrix}$
4	$ \begin{smallmatrix}\left\{ \frac{10}{64}, \frac{44}{64}, \frac{10}{64}\right\} _{k=-1}^{1}\end{smallmatrix}$	$\begin{smallmatrix}\left\{ \frac{20}{64},\frac{40}{64}, \frac{4}{64}\right\} _{k=-1}^{1}\end{smallmatrix}$
5	$ \begin{smallmatrix}\left\{ \frac{15}{256}, \frac{135}{256}, \frac{101}{256}, \frac{5}{256}\right\} _{k=-1}^{2}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{35}{256}, \frac{155}{256}, \frac{65}{256}, \frac{1}{256}\right\} _{k=-1}^{2}\end{smallmatrix}$
6	$ \begin{smallmatrix}\left\{ \frac{6}{1024}, \frac{216}{1024}, \frac{580}{1024}, \frac{6}{1024}\right\} _{k=-2}^{1}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{21}{1024}, \frac{336}{1024}, \frac{546}{1024},\frac{120}{1024}, \frac{1}{1024}\right\} _{k=-2}^{2}\end{smallmatrix}$

$m$	$\ell =2$	$\ell =3$
2	$ \begin{smallmatrix}\left\{ \frac{2}{4}, \frac{2}{4}\right\} _{k=-1}^{0}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{3}{4}, \frac{1}{4}\right\} _{k=-1}^{0}\end{smallmatrix}$
3	$ \begin{smallmatrix}\left\{ \frac{3}{16}, \frac{12}{16}, \frac{1}{16}\right\} _{k=-1}^{1}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{6}{16}, \frac{10}{16}\right\} _{k=-1}^{0}\end{smallmatrix}$
4	$ \begin{smallmatrix}\left\{ \frac{1}{64}, \frac{31}{64}, \frac{31}{64}, \frac{1}{64} \right\} _{k=-2}^{1}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{4}{64}, \frac{40}{64}, \frac{20}{64}\right\} _{k=-2}^{0}\end{smallmatrix}$
5	$ \begin{smallmatrix}\left\{ \frac{1}{256}, \frac{65}{256}, \frac{155}{256}, \frac{35}{256}\right\} _{k=-2}^{1}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{5}{256}, \frac{101}{256}, \frac{135}{256}, \frac{15}{256}\right\} _{k=-2}^{1}\end{smallmatrix}$
6	$ \begin{smallmatrix}\left\{ \frac{56}{1024}, \frac{546}{1024}, \frac{456}{1024}, \frac{56}{1024}\right\} _{k=-2}^{1}\end{smallmatrix}$	$ \begin{smallmatrix}\left\{ \frac{1}{1024}, \frac{120}{1024}, \frac{546}{1024}, \frac{336}{1024}, \frac{21}{1024}\right\} _{k=-3}^{1}\end{smallmatrix}$

Table 3. The weight sequences $\{ w^{[\ell ]}_{m,4}(k)\} $.

The subdivision formulation 3.73 shows that there is a $d$-fold increase in the “number" of subdivision points if the iteration level is increased from $r$ to $r+1$, in the sense that, for any fixed $j\in \mathbb {Z}$, the “old" point $c^{[r]}(j)$ is replaced by the altogether $d$ “new" (or updated) points $\big\{ c^{[r+1]}_{m,d}\big(dj+\ell \big):\ell = 0,\ldots ,d-1\big\} $. Also, note that the resulting increase in computation for increasing values of $d$ is counteracted by the faster geometric convergence rates in 3.66 of Corollary 3.1, with decreasing geometric constants $\frac{1}{d}$ and $\frac{1}{d^2}$ for, respectively, odd and even values of the spline order $m$.

4 Cardinal B-spline graph rendering

Let the control point sequence ${\bf c} \in \ell ^{\infty }(\mathbb {Z})$ in Corollary 3.1 be chosen as ${\bf c} = {\bm@general \boldmath \m@ne \mv@bold \bm@command \delta } = \{ \delta (k)\} \in \ell _{0}(\mathbb {Z})$, the Kronecker delta sequence, for which 3.40 and 3.41 imply

\begin{equation} \label{Eq:4.5} \| \Delta {\bm@general \boldmath \m@ne \mv@bold \bm@command \delta }\| _\infty = 1 ; \qquad \| \Delta ^2 {\bm@general \boldmath \m@ne \mv@bold \bm@command \delta }\| _\infty =2. \end{equation}

4.75

Also, from 3.38, we have

\begin{equation} \label{Eq:4.6} \Phi _{{\bm@general \boldmath \m@ne \mv@bold \bm@command \delta },m} = \phi _{m}. \end{equation}

4.76

If follows from Corollary 3.1 that, for the control point sequence choice ${\bf c} = {\bm@general \boldmath \m@ne \mv@bold \bm@command \delta }$, the subdivision scheme 3.61, 3.62 renders the graph of the centered cardinal B-spline $\phi _{m}$, with in particular, for $m\geq 3$, from 3.66 and 4.75, geometric convergence rates

\begin{equation} \label{Eq:4.7} \displaystyle \sup _j \big| \phi _{m} \big( \tfrac {j}{d^r} \big) - c^{[r]}_{m,d}(j)\big| \leq \left\{ \begin{array}{llll} \displaystyle \tfrac {m-2}{2}\big(\tfrac {1}{d} \big)^r, & {\rm if} \ \ m \ \ {\rm is \ \ odd}; \\[2mm] \displaystyle \tfrac {m}{12}\big(\tfrac {1}{d^2} \big)^r, & {\rm if} \ \ m \ \ {\rm is \ \ even}, \end{array} \right. r=0,1,\ldots \end{equation}

4.77

As noted before in the more general setting of Remark 3.1 (b), the graph of $\phi _{m}$ is rendered by plotting the co-ordinate sequence $\displaystyle \big\{ \big( \tfrac {j}{d^r}, c^{[r]}_{m,d}(j) \big):j\in \mathbb {Z}\big\} $ for a sufficiently large value of the integer $r$.

Our graphical implementation will depend on the following result.

Theorem 4.1

For any integers $m\geq 3$ and $d\geq 2$, the sequences $\big\{ c^{[r]}_{m,d}(k)\big\} \in \ell (\mathbb {Z})$, $r=1,2,\ldots ,$ as generated iteratively by the cardinal spline $d$-ary subdivision scheme 3.61, 3.62, with control point sequence ${\bf c} = \{ c(k)\} = \{ \delta (k)\} \in \ell _{0}(\mathbb {Z})$, satisfy the alternative recursion formulation

\begin{align} \label{Eq:4.8} c^{[1]}_{m,d}(j) = & p_{m,d}(j), \quad j\in \mathbb {Z}; \\ \label{Eq:4.9} c^{[r+1]}_{m,d}(j) = & \displaystyle \sum _k p_{m,d}(k)c^{[r]}_{m,d}(j-d^{r}k), \quad j\in \mathbb {Z}; \quad \quad r=1,2,\ldots . \end{align}

Moreover, $\Big\{ c^{[r]}_{m,d}(k)\Big\} \in \ell _{0}(\mathbb {Z})$, $r=1,2,\ldots $, where

\begin{align} \label{Eq:4.10} c^{[r]}_{m,d}\Big(- (d^{r}-1)\lfloor \tfrac {m}{2}\rfloor \Big) = & \Big( p_{m,d}\big(-(d-1)\lfloor \tfrac {m}{2}\rfloor \big) \Big)^r, \quad r=1,2,\ldots \end{align}

\begin{align} c^{[r]}_{m,d}\Big((d^{r}-1)\lfloor \tfrac {m+1}{2}\rfloor \Big) = & \left( p_{m,d}\Big((d-1)\lfloor \tfrac {m+1}{2}\rfloor \Big) \right)^r,\quad r=1,2,\ldots \nonumber \end{align}

and with support

\begin{equation} \label{Eq:4.11} {\rm supp} \ \Big\{ c^{[r]}_{m,d}(j)\Big\} = \Big[-(d^r-1)\lfloor \tfrac {m}{2}\rfloor , (d^r-1)\lfloor \tfrac {m+1}{2}\rfloor \Big]\cap \mathbb {Z}, \quad r=1,2,\ldots \end{equation}

4.81

Proof â–¼

First, observe that 4.78 is obtained by setting ${\bf c} = \{ c(k)\} = \{ \delta (k)\} $ in 3.61, 3.62. It then follows from 4.78, together with the case $r=1$ of 3.61, 3.62, that

\[ c^{[2]}_{m,d}(j) = \displaystyle \sum _k p_{m,d}(j-dk)p_{m,d}(k), \quad j\in \mathbb {Z}, \]

which shows that 4.79 holds for $r=1$.

Proceeding inductively, we next assume that 4.79 holds for a fixed integer $r\in \mathbb {N}$. By also applying 3.61, 3.62, we deduce that, for any $j\in \mathbb {Z}$,

\begin{align*} c^{[r+2]}_{m,d}(j)& = \displaystyle \sum _k p_{m,d}(j-dk)c^{[r+1]}_{m,d}(k) \\ & = \displaystyle \sum _k p_{m,d}(j-dk)\left\{ \sum _\ell p_{m,d}(\ell ) c^{[r]}_{m,d}\big(k-d^{r}\ell \big) \right\} \nonumber \\ & = \sum _\ell p_{m,d}(\ell )\left\{ \displaystyle \sum _k p_{m,d}(j-dk)c^{[r]}_{m,d}\big(k-d^{r}\ell \big) \right\} \nonumber \\ & = \sum _\ell p_{m,d}(\ell )\left\{ \displaystyle \sum _k p_{m,d}\Big(j-d^{r+1}\ell -dk\Big)c^{[r]}_{m,d}(k) \right\} \nonumber \\ & = \sum _\ell p_{m,d}(\ell )c^{[r+1]}_{m,d}\Big(j-d^{r+1}\ell \Big),\nonumber \end{align*}

which advances the inductive hypothesis from $r$ to $r+1$, and thereby completing our inductive proof of 4.78.

Our next step is to prove inductively that, for $r\in \mathbb {N}$,

\begin{equation} \label{Eq:4.12} c^{[r]}_{m,d}(j)=0, \quad j\in \mathbb {Z}\backslash \Big\{ -(d^r-1)\lfloor \tfrac {m}{2}\rfloor , \ldots ,(d^r-1)\lfloor \tfrac {m+1}{2}\rfloor \Big\} . \end{equation}

4.78

After noting from 4.78 and 2.21 that 4.78 holds for $r=1$, we next fix $r\in \mathbb {N}$, and apply 4.79, together with 2.21, to obtain

\begin{equation} \label{Eq:4.13} c^{[r+1]}_{m,d}(j) = \displaystyle \sum _{k=-(d-1)\lfloor \frac{m}{2}\rfloor }^{(d-1)\lfloor \frac{m+1}{2}\rfloor } p_{m,d}(k)c^{[r]}_{m,d}(j-d^{r}k), \quad j\in \mathbb {Z}. \end{equation}

4.79

Since

\[ j-d^{r}k {\lt} - (d^r-1)\lfloor \tfrac {m}{2}\rfloor , \quad k = -(d-1)\lfloor \tfrac {m}{2}\rfloor , \ldots , (d-1)\lfloor \tfrac {m+1}{2}\rfloor , \]

if and only if

\[ j {\lt} d^r\Big(- (d-1)\lfloor \tfrac {m}{2}\rfloor \Big) - (d^r-1)\lfloor \tfrac {m}{2}\rfloor = - \Big(d^{r+1}-1\Big)\lfloor \tfrac {m}{2}\rfloor , \]

whereas

\[ j-d^{r}k {\gt} (d^r-1)\lfloor \tfrac {m+1}{2}\rfloor , \quad k = -(d-1)\lfloor \tfrac {m}{2}\rfloor , \ldots , (d-1)\lfloor \tfrac {m+1}{2}\rfloor , \]

if and only if

\[ j {\gt} d^r\Big((d-1)\lfloor \tfrac {m+1}{2}\rfloor \Big)+ (d^r-1)\lfloor \tfrac {m+1}{2}\rfloor = \Big(d^{r+1}-1\Big)\lfloor \tfrac {m+1}{2}\rfloor , \]

it follows from 4.79, together with the inductive hypothesis 4.78, that 4.78 is also satisfied with $r$ replaced by $r+1$, which then completes our inductive proof of the fact that 4.78 holds for all $r\in \mathbb {N}$.

It therefore remains to prove 4.80, which, together with 2.21 and 4.78, would then imply the support property 4.81.

To this end, we first note from 4.78 that 4.80 holds for $r=1$. Now let $r\in \mathbb {N}$ be fixed, and apply 4.79 to obtain

\begin{equation} \label{Eq:4.14} \begin{array}{llll} c^{[r+1]}_{m,d}\Big(\! -\! (d^{r+1}\! -\! 1)\lfloor \frac{m}{2}\rfloor \Big) = \displaystyle \sum _{k=-(d-1)\lfloor \frac{m}{2}\rfloor }^{(d-1)\lfloor \frac{m+1}{2}\rfloor } p_{m,d}(k)c^{[r]}_{m,d}\Big(-(d^{r+1}-1)\lfloor \tfrac {m}{2}\rfloor -d^{r}k\Big); \\[2mm] c^{[r+1]}_{m,d}\Big((d^{r+1}\! -\! 1)\lfloor \tfrac {m+1}{2}\rfloor \Big) = \displaystyle \sum _{k=-(d-1)\lfloor \frac{m}{2}\rfloor }^{(d-1)\lfloor \frac{m+1}{2}\rfloor } p_{m,d}(k)c^{[r]}_{m,d}\Big((d^{r+1}\! -\! 1)\lfloor \tfrac {m+1}{2}\rfloor \! -\! d^{r}k\Big). \end{array} \end{equation}

4.80

Since, moreover,

\begin{align*} -\big(d^{r+1}-1\big)\lfloor \tfrac {m}{2}\rfloor -d^{r}k \geq & -\big(d^{r}-1\big)\lfloor \tfrac {m}{2}\rfloor \Leftrightarrow k \leq -(d-1)\lfloor \tfrac {m}{2}\rfloor ; \\ \big(d^{r+1}-1\big)\lfloor \tfrac {m+1}{2}\rfloor -d^{r}k \leq & \big(d^{r}-1\big)\lfloor \tfrac {m+1}{2}\rfloor \Leftrightarrow k \geq (d-1)\lfloor \tfrac {m+1}{2}\rfloor , \end{align*}

if follows from 4.80 and 4.78 that

\begin{align*} c^{[r+1]}_{m,d}\Big(- (d^{r+1}-1)\lfloor \tfrac {m}{2}\rfloor \Big) = & p_{m,d}\Big(-(d-1)\lfloor \tfrac {m}{2}\rfloor \Big) c^{[r]}_{m,d}\Big(- (d^{r}-1)\lfloor \tfrac {m}{2}\rfloor \Big); \\ c^{[r+1]}_{m,d}\Big((d^{r+1}\! -\! 1)\lfloor \tfrac {m+1}{2}\rfloor \Big) = & p_{m,d}\Big((d\! -\! 1)\lfloor \tfrac {m+1}{2}\rfloor \Big) c^{[r]}_{m,d}\Big((d^{r}\! -\! 1)\lfloor \tfrac {m+1}{2}\rfloor \Big), \end{align*}

from which 4.80 then follows inductively.

Proof â–¼

In view of Theorem 4.1, we plot, for $r=1,2,\ldots ,$ the coordinate sequence

\begin{equation} \label{Eq:4.15} \left\{ \big( \tfrac {j}{d^r}, c^{[r]}_{m,d}(j)\big):j = -(d^r-1)\lfloor \tfrac {m}{2}\rfloor ,\ldots , (d^r-1)\lfloor \tfrac {m+1}{2}\rfloor \right\} , \end{equation}

4.81

as computed recursively by means of

\begin{align} \label{Eq:4.16} c^{[1]}_{m,d}(j) = & p_{m,d}(j), \quad j = -(d-1)\lfloor \tfrac {m}{2}\rfloor ,\ldots , (d-1)\lfloor \tfrac {m+1}{2}\rfloor ; \\ \label{Eq:4.17} c^{[r+1]}_{m,d}(j) = & \displaystyle \sum _{k = \mu _{m,d}(r)}^{\nu _{m,d}(r)} p_{m,d}(k)c^{[r]}_{m,d}(j-d^{r}k),\\ \nonumber & j = -\big(d^{r+1}-1\big)\lfloor \tfrac {m}{2}\rfloor ,\ldots , \big(d^{r+1}-1\big)\lfloor \tfrac {m+1}{2}\rfloor ; \quad r=1,2,\ldots , \end{align}

where

\begin{align} \label{Eq:4.18} \mu _{m,d}(r) := & \max \Big\{ -(d-1)\lfloor \tfrac {m}{2}\rfloor , \ - \bigl\lfloor \left\{ (d^r-1)\lfloor \tfrac {m+1}{2}\rfloor -j\right\} /d^{r} \bigr\rfloor \Big\} ; \\ \label{Eq:4.19 } \nu _{m,d}(r) := & \min \Big\{ (d-1)\lfloor \tfrac {m+1}{2}\rfloor , \ \bigl\lfloor \left\{ (d^r-1)\lfloor \tfrac {m}{2}\rfloor +j\right\} /d^{r}\bigr\rfloor \Big\} . \end{align}

For a sufficiently large $r\in \mathbb {N}$, the coordinate points 4.81 then render the graph of the centered cardinal B-Spline $\phi _{m}$. The special case $d=2$ of such cardinal B-spline rendering by means of (binary) subdivision was formulated previously in [ 8 , Algorithm 4.3.1 ] . Graphical illustrations are provided in Figure 4.–4. for $m\in \{ 3,4\} $ and $d\in \{ 2,3,4\} $, and demonstrate the faster geometric convergence rates in 3.73 for increasing values of $d$.

\includegraphics[width=\textwidth ]{./figures1/phi2r=1.jpg} — Figure 4. The subdivision points $\{ c^{[r]}_{3,2}\} $ for rendering the graph of $\phi _{3}$.

\includegraphics[width=\textwidth ]{./figures1/phi2r=2.jpg} — Figure 4. The subdivision points $\{ c^{[r]}_{3,2}\} $ for rendering the graph of $\phi _{3}$.

\includegraphics[width=\textwidth ]{./figures1/phi4r=1.jpg} — Figure 4. The subdivision points $\{ c^{[r]}_{3,4}\} $ for rendering the graph of $\phi _{3}$.

\includegraphics[width=\textwidth ]{./figures1/phi4r=2.jpg} — Figure 4. The subdivision points $\{ c^{[r]}_{3,4}\} $ for rendering the graph of $\phi _{3}$.

\includegraphics[width=\textwidth ]{./figures1/4phid2r=1.jpg} — Figure 4. The subdivision points $\{ c^{[r]}_{4,2}\} $ for rendering the graph of $\phi _{4}$.

\includegraphics[width=\textwidth ]{./figures1/4phid2r=2.jpg} — Figure 4. The subdivision points $\{ c^{[r]}_{4,2}\} $ for rendering the graph of $\phi _{4}$.

\includegraphics[width=\textwidth ]{./figures1/4phid3r=1.jpg} — Figure 4. The subdivision points $\{ c^{[r]}_{4,3}\} $ for rendering the graph of $\phi _{4}$.

\includegraphics[width=\textwidth ]{./figures1/4phid3r=2.jpg} — Figure 4. The subdivision points $\{ c^{[r]}_{4,3}\} $ for rendering the graph of $\phi _{4}$.

\includegraphics[width=\textwidth ]{./figures1/4phid4r=1.jpg} — Figure 4. The subdivision points $\{ c^{[r]}_{4,4}\} $ for rendering the graph of $\phi _{4}$.

\includegraphics[width=\textwidth ]{./figures1/4phid4r=2.jpg} — Figure 4. The subdivision points $\{ c^{[r]}_{4,4}\} $ for rendering the graph of $\phi _{4}$.

5 Closed Curve Rendering

In this section, we extend the graph rendering subdivision scheme 3.73, 3.72 to the setting of closed parametric curve rendering. To this end, for any given (finite) set of control points $\left\{ {\bf c}(0), \ldots , {\bf c}(M)\right\} \subset \mathbb {R}^{s}$, for $M\geq 2$, where $s=2$ or $s=3$, and with ${\bf c}(0) \neq {\bf c}(M)$, we define the extended control point set ${\bf c} = \{ {\bf c}(k):k\in \mathbb {Z}\} \subset \mathbb {R}^{s}$ by means of periodicity, that is,

\begin{equation} \label{Eq:5.1} {\bf c} (j+M+1) = {\bf c} (j), \quad j\in \mathbb {Z}, \end{equation}

5.86

and for which we shall render the parametric cardinal spline curve $\Phi _{{\bf c},m}:\mathbb {R}\rightarrow \mathbb {R}^{s}$, as given by

\begin{equation} \label{Eq:5.2} \Phi _{{\bf c},m}(x) := \textstyle \sum _{k}{\bf c}(k)\phi _{m} (x-k), \quad x\in \mathbb {R}, \end{equation}

5.87

by means of the $d$-ary $m^{th}$ order cardinal spline subdivision scheme

\begin{equation} \label{Eq:5.3} {\bf c}^{[0]}_{m,d} : = {\bf c}; \qquad {\bf c}^{[r+1]}_{m,d}\big(dj+\ell \big) = \displaystyle \sum _k w^{[\ell ]}_{m,d}(k){\bf c}^{[r]}_{m,d}(j-k), \end{equation}

5.88

$ j\in \mathbb {Z}; \ell =0,\ldots ,d-1; \quad r=0,1,\ldots ,$ where the weight sequences $\big\{ w^{[\ell ]}_{m,d}(k) \big\} \in \ell _{0}(\mathbb {Z})$, $\ell = 0,\ldots ,d-1$, are defined by 3.72 in terms of the refinement sequence $\{ p_{m,d}(k)\} \in \ell _{0}(\mathbb {Z})$ of Theorem 2.1.

We shall rely on the fact that the periodicity property 5.86 of the control point sequence ${\bf c} = \{ {\bf c}(k):k\in \mathbb {Z}\} \subset \mathbb {R}^{s}$ is preserved as follows by cardinal spline $d$-ary subdivision.

Theorem 5.1

Let ${\bf c} = \{ {\bf c}(k):k\in \mathbb {Z}\} \in \mathbb {R}^{s}$, with $s=2$ or $s=3$, denote a control point sequence satisfying the periodicity condition 5.86 for some integer $M \geq 2$. Then, for any integers $m \geq 2$ and $d \geq 2$, the $d$-ary $m^{th}$ order cardinal spline subdivision sequences $\big\{ {\bf c}^{[r]}_{m,d}:r = 0,1\ldots ,\big\} $, as generated recursively by means of 3.61, 3.62, are also periodic, with

\begin{equation} \label{Eq:5.4} {\bf c}^{[r]}\big(j+ d^r(M+1)\big) = {\bf c}^{[r]} (j), \quad j\in \mathbb {Z}, \quad r = 1,2\ldots , \end{equation}

5.89

and the parametric cardinal spline curve $ \Phi _{{\bf c},m}:\mathbb {R}\rightarrow \mathbb {R}^{s}$, as given in 5.87, satisfies the periodicity condition

\begin{equation} \label{Eq:5.5} \Phi _{{\bf c},m}\big(x+ M+1\big) = \Phi _{{\bf c},m}(x), \quad x\in \mathbb {R}, \end{equation}

5.90

according to which $\Phi _{{\bf c},m}$ is a closed parametric curve in $\mathbb {R}^{s}$.

Proof â–¼

By applying the subdivision formulation 3.61, 3.62, we deduce

that, for any fixed $j\in \mathbb {Z}$,

\begin{align} \label{Eq:5.6} {\bf c}^{[r+1]}\Big(j+ d^{r+1}(M+1)\Big) & =\displaystyle \sum _k p_{m,d}\Big(j-d\{ k-d^{r}(M+1)\} \Big)c^{[r]}(k) \nonumber \\ & =\displaystyle \sum _k p_{m,d}(j\! -\! dk){\bf c}^{[r]}\big(k\! +\! d^{r}(M\! +\! 1)\big), \quad r=0,1, \ldots . \end{align}

The periodicity result 5.89 now follows inductively from 5.91 and 5.86.

Next, we apply 5.87 and 5.86 to deduce that, for any $x\in \mathbb {R}$,

\begin{align*} \Phi _{{\bf c},m}\big(x+ M+1\big) & = \displaystyle \sum _{k}c(k)\phi _{m}\big(x-\{ k-(M+1)\} \big) \\ & =\displaystyle \sum _{k}c(k\! +\! M\! +\! 1)\phi _{m}(x-k)\! =\! \displaystyle \sum _{k}c(k)\phi _{m}(x\! -\! k)\! =\! \Phi _{{\bf c},m}(x), \end{align*}

which completes our proof of 5.90.

Proof â–¼

Since the periodicity condition 5.86 implies that, for any given (finite) control point sequence $\left\{ {\bf c}(0), \ldots , {\bf c}(M)\right\} \subset \mathbb {R}^{s}$, its extension 5.86 is a bounded sequence in $\mathbb {R}^{s}$, we may now apply the extension to the $\mathbb {R}^{s}$-parametric curve setting of Corollary 3.1, together with Theorem 5.1, for the rendering of the closed cardinal spline parametric curve $\Phi _{{\bf c},m}:\mathbb {R}\rightarrow \mathbb {R}^{s}$ given by 5.87. Observe from 5.87 and 2.6 that $\Phi _{{\bf c},m}$ is a $C^{m-2}$-smooth curve in $\mathbb {R}^{s}$. Also, for $m\geq 3$, the curve $\Phi _{{\bf c},m}$ is “corner-cutting" with respect to the control points $\left\{ {\bf c}(0), \ldots , {\bf c}(M)\right\} $.

With the view to graphical implementation, for any integers $d \geq 2$, $m\geq 3$ and
$M\geq \max \Big\{ 2, \lfloor \{ (d-1)(\lfloor \tfrac {m}{2}\rfloor +1)\} /d\rfloor \Big\} $, let $\left\{ {\bf c}(0) \ldots , {\bf c}(M)\right\} $, denote an arbitrarily chosen ordered sequence of control points in $\mathbb {R}^{s}$, for $s=2$ or $s=3$, and with ${\bf c}(0) \neq {\bf c}(M)$. Based on the alternative formulation 3.73, 3.72, together with 3.74, as well as 5.89 in Theorem 5.1, we plot, for $r=0,1,\ldots $, the subdivision sequence

\begin{align} \label{Eq:5.7} \Big\{ {\bf c}^{[r]}_{m,d}(j): j= 0, \ldots ,d^{r}(M+1)-1\Big\} , \end{align}

as recursively computed by means of

\[ {\bf c}^{[0]}_{m,d}(j) : = {\bf c}(j), \quad j= 0, \ldots ,M; \]

and

\begin{align} \label{Eq:5.8} {\bf c}^{[r+1]}_{m,d}\big(dj+\ell \big) := \displaystyle \sum _{k=-\lfloor \{ (d-1)\lfloor \frac{m}{2}\rfloor + \ell \} /d\rfloor }^{\lfloor \{ (d-1)\lfloor \frac{m+1}{2}\rfloor - \ell \} /d\rfloor } w^{[\ell ]}_{m,d}(k){\bf c}^{[r]}(j-k); \quad \ell =0,\ldots ,d-1, \nonumber \\ \quad j= 0, \ldots ,d^{r}(M+1)-1, \end{align}

where

\begin{align} \label{Eq:5.9} {\bf c}^{[r]}_{m,d}(j) := {\bf c}^{[r]}\big(j+d^{r}(M+1)\big), \quad j= -\lfloor \{ (d-1)\lfloor \tfrac {m+1}{2}\rfloor \} /d\rfloor , \ldots ,-1; \\ \label{Eq:5.10} {\bf c}^{[r]}_{m,d}\big(d^{r}(M+1)-1+j\big):={\bf c}^{[r]}(j-1), \quad j=1, \ldots , \lfloor \{ (d-1)(\lfloor \tfrac {m}{2}\rfloor +1)\} /d\rfloor . \end{align}

For sufficiently large $r\in \mathbb {N}$, the points 5.92 then render the graph of the closed parametric cardinal spline curve $\Phi _{{\bf c},m}:\mathbb {R}\rightarrow \mathbb {R}^{s}$, as given by 5.87, with control point sequence extended periodically as in 5.86. The special case $d=2$ of the closed curve rendering scheme 5.92–5.95 was previously formulated for general binary subdivision in [ 8 , Algorithm 3.3.1 (a), (b) ] .

Graphical illustrations are given in Figures 5.–5., for $m\in \{ 4,6\} $ and $d\in \{ 2,3,4\} $, and demonstrates, also in the setting of parameter curve rendering, the faster geometric convergence rates in 3.67 in Corollary 3.1 for increasing values of $d$, as well as the improved curve smoothness for increasing values of the spline order $m$.

\includegraphics[width=\textwidth ]{./figures1/dsubr=0.jpg} — Figure 5. The subdivision points $\{ {\bf c}^{[r]}_{4,2}\} $ for rendering the parametric curve $\Phi _{{\bf c},4}$.

\includegraphics[width=\textwidth ]{./figures1/d2subr=1.jpg} — Figure 5. The subdivision points $\{ {\bf c}^{[r]}_{4,2}\} $ for rendering the parametric curve $\Phi _{{\bf c},4}$.

\includegraphics[width=\textwidth ]{./figures1/d3subr=1.jpg} — Figure 5. The subdivision points $\{ {\bf c}^{[r]}_{4,3}\} $ for rendering the parametric curve $\Phi _{{\bf c},4}$.

\includegraphics[width=\textwidth ]{./figures1/d4subr=1.jpg} — Figure 5. The subdivision points $\{ {\bf c}^{[r]}_{4,4}\} $ for rendering the parametric curve $\Phi _{{\bf c},4}$.

\includegraphics[width=\textwidth ]{./figures1/m6d2subr=1.jpg} — Figure 5. The subdivision points $\{ {\bf c}^{[r]}_{6,2}\} $ for rendering the parametric curve $\Phi _{{\bf c},6}$.

\includegraphics[width=\textwidth ]{./figures1/m6d3subr=1.jpg} — Figure 5. The subdivision points $\{ {\bf c}^{[r]}_{6,3}\} $ for rendering the parametric curve $\Phi _{{\bf c},6}$.

\includegraphics[width=\textwidth ]{./figures1/m6d4subr=1.jpg} — Figure 5. The subdivision points $\{ {\bf c}^{[r]}_{6,4}\} $ for rendering the parametric curve $\Phi _{{\bf c},6}$.

Bibliography

1: S. S. Siddiqi and M. Younis, The m-point quaternary approximating subdivision schemes, American Journal of Computational Mathematics, 3 (2013) no. 1, pp. 6–10. $\includegraphics[scale=0.1]{ext-link.png}$
2: G. Munting, Symbols and exact regularity of symmetric pseudo-splines of any arity, Bit Numerical Mathematics, 57 (2017) no. 3, pp. 867–900. $\includegraphics[scale=0.1]{ext-link.png}$
3: M. Asghar and G. Mustafa, Family of $a$-ary univariate subdivision schemes generated by Laurent Polynomial, Mathematical Problems in Engineering, 19 (2018), pp. 1–11. $\includegraphics[scale=0.1]{ext-link.png}$
4: K. P. Ko, B.-G. Lee and G. J. Yoon, A ternary 4-point approximating subdivision scheme, Applied Mathematics and Computation, 190 (2007) no. 2, pp. 1563–1573. $\includegraphics[scale=0.1]{ext-link.png}$
5: G. Mustafa and F. Khan, A new 4-point quaternary approximating subdivision scheme, Abstract and Applied Analysis, 2009 (2009) no. 2, pp. 1–14. $\includegraphics[scale=0.1]{ext-link.png}$
6: M. Marsden, An identity for spline functions with applications to variation-diminishing spline approximation, J. Approx. Theory, 3 (1970) no. 1, pp. 7–49. $\includegraphics[scale=0.1]{ext-link.png}$
7: A. Cavaretta, W. Dahmen and C. A. Micchelli, Stationary subdivision, Mem. Amer. Math. Soc., 93 (1991), pp. 1–185.
8: C. Chui and J. de Villiers, Wavelet Subdivision Methods: GEMS for Rendering Curves and Surfaces, CRC Press, Boca Raton, FL, (2010). $\includegraphics[scale=0.1]{ext-link.png}$
9: M. A. Sabin, Analysis and Design of Univariate Subdivision Schemes, Springer Berlin Heidelberg, (2010). $\includegraphics[scale=0.1]{ext-link.png}$
10: C. Conti and K. Hormann, Polynomial reproduction for univariate subdivision schemes of any arity, J. Approx. Theory, 163 (2011) no. 4, pp. 413–437. $\includegraphics[scale=0.1]{ext-link.png}$
11: N. Dyn, J. A. Gregory and D. Levin, Analysis of uniform binary subdivision schemes for curve design, Constr. Approx., 7 (1991) no. 1, pp. 127–147. $\includegraphics[scale=0.1]{ext-link.png}$
12: J. Warren and H. Weimer, Subdivision Methods for Geometric Design: A Constructive Approach, Morgan Kaufmann Publishers Inc., (2001). $\includegraphics[scale=0.1]{ext-link.png}$
13: T. DeRose, M. Kass and T. Truong, Subdivision surfaces in character animation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques - SIGGRAPH ’98, (1998). $\includegraphics[scale=0.1]{ext-link.png}$
14: L. Gori, F. Pitolli and E. Santi, Refinable ripplets with dilation 3, Jaen Journal on Approximation, 3 (2011) no. 2, pp. 173–191.
15: L. Gori, F. Pitolli and E. Santi, On a class of shape-preserving refinable functions with dilation 3, Journal of Computational and Applied Mathematics, 245 (2013), pp. 62–74. $\includegraphics[scale=0.1]{ext-link.png}$
16: M. F. Hassan and N. A. Dodgson, Ternary and three-point univariate subdivision schemes, In A. Cohen, J.-L. Merrien, and L. L. Schumaker (Eds.), Curve and Surface fitting: Saint-Malo 2002, Nashboro Press, (2003), pp. 199–208.
17: R. Q. Jia and B. Han, Multivariate refinement equations and convergence of subdivision schemes, SIAM J. Math. Anal., 29 (1998) no. 5, pp. 1177–1199. $\includegraphics[scale=0.1]{ext-link.png}$
18: R. F. Riesenfeld, On Chaikin’s algorithm, Computer Graphics and Image Processing, 4 (1975), pp. 304–310.
19: K. Rehan and S. Siddiqi, A family of ternary subdivision schemes for curves, Applied Mathematics and Computation, 270 (2015), pp. 114–123. $\includegraphics[scale=0.1]{ext-link.png}$
20: H. Zheng, M. HU and G. Peng, p-ary subdivision generalizing B-splines, Second International Conference on Computer and Electrical Engineering, (2009). $\includegraphics[scale=0.1]{ext-link.png}$
21: T. Popoviciu, Sur quelques propriétés des fonctions d’une ou de deux variables réelles, Mathematica, 8 (1934), pp. 1–85.
22: T. Popoviciu, Sur le prolongement des fonctions convexes d’ordre superieur, Bull. Math. Soc. Roumaine des Sc., 36 (1934), pp. 75–108.
23: I.J. Schoenberg, Contributions to the problem of approximation of equidistant data by analytic functions, Part A: on the problem of smoothing or graduation, a first class of analytic approximation formulas, Quart. Appl. Math., 4 (1946), pp. 45–99. $\includegraphics[scale=0.1]{ext-link.png}$
24: I.J. Schoenberg, On P̀olya frequency functions III. The positivity of translation determinants with an application to the interpolation problem by spline curves, Trans. Amer. Math. Soc., 74 (1953), pp. 246–259. $\includegraphics[scale=0.1]{ext-link.png}$

This work is licensed under a Creative Commons Attribution 4.0 International License.

\(m\)	\(\{ p_{m,2}(k)\} \)	\(\{ p_{m,3}(k)\} \)
2	\(\begin{smallmatrix}\left\{ \frac{1}{2}\! , 1\! , \frac{1}{2}\right\} _{k=-1}^{1}\end{smallmatrix}\)	\(\begin{smallmatrix}\left\{ \frac{1}{3}\! ,\frac{2}{3}\! ,1\! ,\frac{2}{3}\! ,\frac{1}{3}\right\} _{k=-2}^{2}\end{smallmatrix}\)
3	\(\begin{smallmatrix}\left\{ \frac{1}{4}\! , \frac{3}{4}\! , \frac{3}{4}\! , \frac{1}{4}\right\} _{k=-1}^{2}\end{smallmatrix}\)	\(\begin{smallmatrix}\left\{ \frac{1}{9}\! ,\frac{3}{9}\! ,\frac{6}{9}\! ,\frac{7}{9}\! ,\frac{6}{9}\! ,\frac{3}{9}\! ,\frac{1}{9}\right\} _{k=-2}^{4}\end{smallmatrix}\)
4	\(\begin{smallmatrix}\left\{ \frac{1}{8}\! , \frac{4}{8}\! , \frac{6}{8}\! , \frac{4}{8}\! , \frac{1}{8}\right\} _{k=-2}^{2}\end{smallmatrix}\)	\(\begin{smallmatrix}\left\{ \frac{1}{27}\! ,\frac{4}{27}\! ,\frac{10}{27}\! ,\frac{16}{27}\! ,\frac{19}{27}\! ,\frac{16}{27}\! ,\frac{10}{27}\! ,\frac{4}{27}\! ,\frac{1}{27}\right\} _{k=-4}^{4}\end{smallmatrix}\)
5	\(\begin{smallmatrix}\left\{ \frac{1}{16}\! ,\frac{5}{16}\! ,\frac{10}{16}\! ,\frac{10}{16}\! ,\frac{5}{16}\! ,\frac{1}{16}\right\} _{k=-2}^{3}\end{smallmatrix}\)	\(\begin{smallmatrix} \left\{ \frac{1}{81}\! ,\frac{5}{81}\! ,\frac{15}{81}\! ,\frac{30}{81}\! ,\frac{45}{81}\! ,\frac{51}{81}\! ,\frac{45}{81}\! ,\frac{30}{81}\! ,\frac{15}{81}\! ,\frac{5}{81}\! ,\frac{1}{81}\right\} _{k=-4}^{6}\end{smallmatrix}\)
6	\(\begin{smallmatrix}\left\{ \frac{1}{32}\! ,\frac{6}{32}\! ,\frac{15}{32}\! ,\frac{20}{32}\! ,\frac{15}{32}\! ,\frac{6}{32}\! ,\frac{1}{32}\right\} _{k=-3}^{3}\end{smallmatrix}\)	\( \begin{smallmatrix} \left\{ \frac{1}{243}\! ,\frac{6}{243}\! ,\frac{21}{243}\! ,\frac{50}{243}\! ,\frac{90}{243}\! ,\frac{126}{243}\! ,\frac{141}{243}\! ,\frac{126}{243}\! ,\frac{90}{243}\! ,\frac{50}{243}\! ,\frac{21}{243}\! ,\frac{6}{243}\! ,\frac{1}{243}\right\} _{k=-6}^{6} \end{smallmatrix} \)

\(m\)	\(\ell =0\)	\(\ell =1\)
2	\( \begin{smallmatrix} \{ 1\} _{k=0} \end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{1}{2}, \frac{1}{2}\right\} _{k=-1}^{0} \end{smallmatrix}\)
3	\( \begin{smallmatrix}\left\{ \frac{3}{4}, \frac{1}{4}\right\} _{k=0}^{1}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{1}{4}, \frac{3}{4}\right\} _{k=-1}^{0}\end{smallmatrix}\)
4	\( \begin{smallmatrix}\left\{ \frac{1}{8}, \frac{6}{8}, \frac{1}{8}\right\} _{k=-1}^{1}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{4}{8},\frac{4}{8}\right\} _{k=-1}^{0}\end{smallmatrix}\)
5	\( \begin{smallmatrix}\left\{ \frac{1}{16}, \frac{10}{16}, \frac{5}{16}\right\} _{k=-1}^{1}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{5}{16}, \frac{10}{16}, \frac{1}{16}\right\} _{k=-1}^{1}\end{smallmatrix}\)
6	\( \begin{smallmatrix}\left\{ \frac{6}{32}, \frac{20}{32}, \frac{6}{32}\right\} _{k=-1}^{1}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{1}{32}, \frac{15}{32}, \frac{15}{32},\frac{1}{32}\right\} _{k=-2}^{1}\end{smallmatrix}\)

\(m\)	\(\ell =0\)	\(\ell =1\)
2	\( \begin{smallmatrix}\{ 1\} _{k=0}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{1}{4}, \frac{3}{4}\right\} _{k=-1}^{0}\end{smallmatrix}\)
3	\( \begin{smallmatrix}\left\{ \frac{10}{16}, \frac{6}{16}\right\} _{k=0}^{1}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{1}{16}, \frac{12}{16}, \frac{3}{16}\right\} _{k=-1}^{1}\end{smallmatrix}\)
4	\( \begin{smallmatrix}\left\{ \frac{10}{64}, \frac{44}{64}, \frac{10}{64}\right\} _{k=-1}^{1}\end{smallmatrix}\)	\(\begin{smallmatrix}\left\{ \frac{20}{64},\frac{40}{64}, \frac{4}{64}\right\} _{k=-1}^{1}\end{smallmatrix}\)
5	\( \begin{smallmatrix}\left\{ \frac{15}{256}, \frac{135}{256}, \frac{101}{256}, \frac{5}{256}\right\} _{k=-1}^{2}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{35}{256}, \frac{155}{256}, \frac{65}{256}, \frac{1}{256}\right\} _{k=-1}^{2}\end{smallmatrix}\)
6	\( \begin{smallmatrix}\left\{ \frac{6}{1024}, \frac{216}{1024}, \frac{580}{1024}, \frac{6}{1024}\right\} _{k=-2}^{1}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{21}{1024}, \frac{336}{1024}, \frac{546}{1024},\frac{120}{1024}, \frac{1}{1024}\right\} _{k=-2}^{2}\end{smallmatrix}\)

\(m\)	\(\ell =2\)	\(\ell =3\)
2	\( \begin{smallmatrix}\left\{ \frac{2}{4}, \frac{2}{4}\right\} _{k=-1}^{0}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{3}{4}, \frac{1}{4}\right\} _{k=-1}^{0}\end{smallmatrix}\)
3	\( \begin{smallmatrix}\left\{ \frac{3}{16}, \frac{12}{16}, \frac{1}{16}\right\} _{k=-1}^{1}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{6}{16}, \frac{10}{16}\right\} _{k=-1}^{0}\end{smallmatrix}\)
4	\( \begin{smallmatrix}\left\{ \frac{1}{64}, \frac{31}{64}, \frac{31}{64}, \frac{1}{64} \right\} _{k=-2}^{1}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{4}{64}, \frac{40}{64}, \frac{20}{64}\right\} _{k=-2}^{0}\end{smallmatrix}\)
5	\( \begin{smallmatrix}\left\{ \frac{1}{256}, \frac{65}{256}, \frac{155}{256}, \frac{35}{256}\right\} _{k=-2}^{1}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{5}{256}, \frac{101}{256}, \frac{135}{256}, \frac{15}{256}\right\} _{k=-2}^{1}\end{smallmatrix}\)
6	\( \begin{smallmatrix}\left\{ \frac{56}{1024}, \frac{546}{1024}, \frac{456}{1024}, \frac{56}{1024}\right\} _{k=-2}^{1}\end{smallmatrix}\)	\( \begin{smallmatrix}\left\{ \frac{1}{1024}, \frac{120}{1024}, \frac{546}{1024}, \frac{336}{1024}, \frac{21}{1024}\right\} _{k=-3}^{1}\end{smallmatrix}\)

Geometric Convergence Rates for Cardinal Spline Subdivision with General Integer Arity

1 Introduction

2 Centered Cardinal B-splines

3 Geometrically Convergent Subdivision

4 Cardinal B-spline graph rendering

5 Closed Curve Rendering

Bibliography

Geometric Convergence Rates
for Cardinal Spline Subdivision
with General Integer Arity