Return to Article Details Geometric convergence rates for cardinal spline subdivision with general integer arity

Geometric Convergence Rates
for Cardinal Spline Subdivision
with General Integer Arity

Johan de Villiers $^{* ∙}$ Mpfareleni Rejoyce Gavhi-Molefe $^{*}$

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

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

$^{∙}$ 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^{t h}$ order centered cardinal B-spline $ϕ_{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 $R^{s}$ , for $s = 2$ or $s = 3$ .

2 Centered Cardinal B-splines

For any positive integer $m$ , the function $N_{m} : R \to R$ defined recursively by means of

N_{1} (x) := {\begin{matrix} 1, & x \in [0, 1); \\ 0, & x \in R ∖ [0, 1); \end{matrix} N_{m + 1} (x) := \int_{0}^{1} N_{m} (x - t) d t, x \in R, m = 1, 2, \dots,

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

ϕ_{m} (x) := N_{m} (x + ⌊ \frac{m}{2} ⌋), x \in R,

2.2

with $⌊ a ⌋$ denoting the largest integer $\leq a$ , then yields the function $ϕ_{m} : R \to R$ , which we shall call the centered cardinal B-spline of order $m$ . Observe from 2.2 that $ϕ_{1} = N_{1}$ , whereas $ϕ_{2}$ is the linear hat function, that is,

ϕ_{2} (x) := {\begin{matrix} 1 - | x |, & x \in [- 1, 1); \\ 0, & x \in R ∖ [- 1, 1) . \end{matrix}

2.3

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

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

$ϕ_{m}$ is a compactly supported function, with support interval

$s u p p ϕ_{m} = [- ⌊ \frac{m}{2} ⌋, ⌊ \frac{m + 1}{2} ⌋];$
2.4
$ϕ_{m}$ is a piecewise polynomial, with

$ϕ_{m} |_{[k, k + 1)} \in π_{m - 1}, k \in Z;$
2.5
$ϕ_{m}$ satisfies the smoothness condition

$ϕ_{m} \in C_{0}^{m - 2} (R);$
2.6
$ϕ_{m}$ has the positivity property

$ϕ_{m} (x) > 0, x \in (- ⌊ \frac{m}{2} ⌋, ⌊ \frac{m + 1}{2} ⌋);$
2.7
the unit integral and partition of unity properties

$\int_{- \infty}^{\infty} ϕ_{m} (t) d t = \sum_{k} ϕ_{m} (x - k) = 1, x \in R;$
2.8

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

$\sum_{k} ϕ_{m} (k) = 1;$
2.9
the symmetry properties

$\begin{aligned} ϕ_{m} (- x) = & ϕ_{m} (x) x \in R, i f m i s e v e n; \\ ϕ_{m} (1 - x) = & ϕ_{m} (x), x \in R, i f m i s o d d, m \geq 3, \end{aligned}$

or, equivalently,

$ϕ_{m} (\frac{1}{2} + x) = ϕ_{m} (\frac{1}{2} - x), x \in R, i f m i s o d d, m \geq 3,$
2.12

are satisfied;
$ϕ_{m}$ is a refinable function, with

$ϕ_{m} (x) = \sum_{k} p_{m} (k) ϕ_{m} (2 x - k), x \in R,$
2.13

with refinement sequence given by

$p_{m} (k) := \frac{1}{2^{m - 1}} (\binom{m}{k + ⌊ \frac{m}{2} ⌋}), k \in Z,$
2.14

where $(\binom{j}{ℓ}) := 0, ℓ \notin {0, \dots, j}$ , and with the support of the sequence ${p_{m} (k)}$ given by

$s u p p {p_{m} (k)} = [- ⌊ \frac{m}{2} ⌋, ⌊ \frac{m + 1}{2} ⌋] \cap Z .$
2.15

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

P_{m} (z) := \frac{1}{2} \sum_{k} p_{m} (k) z^{k},

2.16

is given by

P_{m} (z) = z^{- ⌊ \frac{m}{2} ⌋} (\frac{1 + z}{2})^{m} .

2.17

In our subdivision analysis of this paper, we shall rely on the fact that the refinement properties 2.13–2.17 of $ϕ_{m}$ can be extended as follows.

Theorem 2.1

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

ϕ_{m} (x) = \sum_{k} p_{m, d} (k) ϕ_{m} (d x - k), x \in R,

2.18

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

\frac{1}{d} \sum_{k} p_{m, d} (k) z^{k} = P_{m, d} (z),

2.19

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

P_{m, d} (z) := z^{- (d - 1) ⌊ \frac{m}{2} ⌋} (\frac{1 + z + \dots + z^{d - 1}}{d})^{m},

2.20

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

s u p p {p_{m, d} (k)} = [- (d - 1) ⌊ \frac{m}{2} ⌋, (d - 1) ⌊ \frac{m + 1}{2} ⌋] \cap Z .

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

N_{1} (x) = \sum_{k} p (k) N_{1} (d x - k), x \in R,

2.22

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

p (k) := {\begin{matrix} 1, & k = 0, \dots, d - 1; \\ 0, & k \in Z ∖ {0, \dots, d - 1} . \end{matrix}

2.23

Also, the corresponding Laurent polynomial $P$ defined by

P (z) := \frac{1}{d} \sum_{k} p (k) z^{k},

2.24

is then given by

P (z) = \frac{1 + z + \dots + z^{d - 1}}{d} .

2.25

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

N_{m} (x) = \sum_{k} {\tilde{p}}_{m, d} (k) N_{m} (d x - k), x \in R,

2.26

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

\sum_{k} {\tilde{p}}_{m, d} (k) z^{k} = \frac{1}{d^{m - 1}} (1 + z + \dots + z^{d - 1})^{m} .

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 N$ .

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

\sum_{k} p^{*} (k) z^{k} := \frac{1}{d^{m}} (1 + z + \dots + z^{d - 1})^{m + 1} .

2.28

It follows from 2.27 and 2.28 that

p^{*} (k) = \frac{1}{d} \sum_{j = 0}^{d - 1} {\tilde{p}}_{m, d} (k - j), k \in Z .

2.29

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

\begin{aligned} \sum_{k} p^{*} (k) N_{m + 1} (d x - k) & = \frac{1}{d} \sum_{k} {\sum_{j = 0}^{d - 1} {\tilde{p}}_{m, d} (k - j)} \int_{0}^{1} N_{m} (d x - k - t) d t \\ = \frac{1}{d} \sum_{j = 0}^{d - 1} \int_{0}^{1} {\sum_{k} {\tilde{p}}_{m, d} (k - j) N_{m} (d x - t - k)} d t \\ = \frac{1}{d} \sum_{j = 0}^{d - 1} \int_{0}^{1} {\sum_{k} {\tilde{p}}_{m, d} (k) N_{m} (d (x - \frac{t + j}{d}) - k)} d t \\ = \frac{1}{d} \sum_{j = 0}^{d - 1} \int_{0}^{1} N_{m} (x - \frac{t + j}{d}) d t \\ = \sum_{j = 0}^{d - 1} \int_{j / d}^{(j + 1) / d} N_{m} (x - t) d t \\ = \int_{0}^{1} N_{m} (x - t) d t = N_{m + 1} (x), \end{aligned}

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

p_{m, d} (k) = {\tilde{p}}_{m, d} (k + (d - 1) ⌊ \frac{m}{2} ⌋), k \in Z .

2.30

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

\begin{aligned} \sum_{k} p_{m, d} (k) ϕ_{m} (d x - k) & = \sum_{k} {\tilde{p}}_{m, d} (k + (d - 1) ⌊ \frac{m}{2} ⌋) N_{m} (d x - k + ⌊ \frac{m}{2} ⌋) \\ = \sum_{k} {\tilde{p}}_{m, d} (k) N_{m} (d (x + ⌊ \frac{m}{2} ⌋) - k) \\ = N_{m} (x + ⌊ \frac{m}{2} ⌋) = ϕ_{m} (x), \end{aligned}

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 $ϕ_{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 Z}$ .

Theorem 2.2

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

\begin{aligned} p_{1, d} (k) = & {\begin{array}{c} 1, \end{array} & k = 0, \dots, d - 1; \\ 0, & k \in Z ∖ {0, \dots, d - 1}; \end{aligned}

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

\end{align}

where

μ_{m} := {\begin{matrix} 1, i f m i s o d d; \\ 0, i f m i s e v e n . \end{matrix}

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

{p_{m, d} (k) : k = - (d - 1) ⌊ \frac{m}{2} ⌋, \dots, (d - 1) ⌊ \frac{m + 1}{2} ⌋},

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

$m$	${p_{m, 2} (k)}$	${p_{m, 3} (k)}$
2	$\begin{matrix} {\frac{1}{2}, 1, \frac{1}{2}}_{k = - 1}^{1} \end{matrix}$	$\begin{matrix} {\frac{1}{3}, \frac{2}{3}, 1, \frac{2}{3}, \frac{1}{3}}_{k = - 2}^{2} \end{matrix}$
3	$\begin{matrix} {\frac{1}{4}, \frac{3}{4}, \frac{3}{4}, \frac{1}{4}}_{k = - 1}^{2} \end{matrix}$	$\begin{matrix} {\frac{1}{9}, \frac{3}{9}, \frac{6}{9}, \frac{7}{9}, \frac{6}{9}, \frac{3}{9}, \frac{1}{9}}_{k = - 2}^{4} \end{matrix}$
4	$\begin{matrix} {\frac{1}{8}, \frac{4}{8}, \frac{6}{8}, \frac{4}{8}, \frac{1}{8}}_{k = - 2}^{2} \end{matrix}$	$\begin{matrix} {\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}}_{k = - 4}^{4} \end{matrix}$
5	$\begin{matrix} {\frac{1}{16}, \frac{5}{16}, \frac{10}{16}, \frac{10}{16}, \frac{5}{16}, \frac{1}{16}}_{k = - 2}^{3} \end{matrix}$	$\begin{matrix} {\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}}_{k = - 4}^{6} \end{matrix}$
6	$\begin{matrix} {\frac{1}{32}, \frac{6}{32}, \frac{15}{32}, \frac{20}{32}, \frac{15}{32}, \frac{6}{32}, \frac{1}{32}}_{k = - 3}^{3} \end{matrix}$	$\begin{matrix} {\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}}_{k = - 6}^{6} \end{matrix}$

Table 2. The sequences

{p_{m, d} (k) : k = - (d - 1) ⌊ \frac{m}{2} ⌋, \dots, (d - 1) ⌊ \frac{m + 1}{2} ⌋}

d = 2, 3

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

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

$\begin{matrix} {\frac{1}{4}, \frac{2}{4}, \frac{3}{4}, 1, \frac{3}{4}, \frac{2}{4}, \frac{1}{4}}_{k = - 3}^{3} \end{matrix}$

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

$\begin{matrix} {\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}}_{k = - 3}^{6} \end{matrix}$

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

$\begin{matrix} {\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}}_{k = - 6}^{6} \end{matrix}$

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

$\begin{matrix} {\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}}_{k = - 6}^{9} \end{matrix}$

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

$\begin{matrix} {\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}}_{- 9}^{9} \end{matrix}$

Table 2. The sequences

{p_{m, d} (k) : k = - (d - 1) ⌊ \frac{m}{2} ⌋, \dots, (d - 1) ⌊ \frac{m + 1}{2} ⌋}

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 Z}$ .

Theorem 2.3

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

\sum_{k} p_{m, d} (d k + ℓ) = 1, ℓ = 0, 1, \dots, d - 1.

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 N

. It then follows from 2.32 that, for any

ℓ \in {0, 1, \dots, d - 1}

\sum_{k} p_{m + 1, d} (d k + ℓ) = \frac{1}{d} \sum_{j = 0}^{d - 1} \sum_{k} p_{m, d} (d k + ℓ - j + (d - 1) μ_{m}) .

2.35

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

ℓ - j + (d - 1) μ_{m} = d q + r;

2.36

according to which then

\sum_{k} p_{m, d} (d k + ℓ - j + (d - 1) μ_{m}) = \sum_{k} p_{m, d} (d (k + q) + r) = \sum_{k} p_{m, d} (d k + r) = 1,

2.37

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

\sum_{k} p_{m + 1, d} (d k + ℓ) = 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 $Φ_{c, m} : R \to R$ , as defined for any given bounded control point sequence $c = {c (k) : k \in Z} \in ℓ (Z)$ by

Φ_{c, m} (x) := \sum_{k} c (k) ϕ_{m} (x - k), x \in R,

3.38

with $ϕ_{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 $R^{s}$ , for $s = 2$ or $s = 3$ , in which case our convergent subdivision scheme renders the corresponding parametric cardinal spline curve in $R^{s}$ .

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

‖ c ‖_{\infty} = ‖ c (k) ‖_{\infty} := sup_{k} | c (k) | < \infty,

3.39

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

Our convergence results below will be formulated in terms of the backwards difference operator $Δ : ℓ (Z) \to ℓ (Z)$ , as defined by

(Δ c) (k) := c (k) - c (k - 1), k \in Z, c = {c (k)} \in ℓ (Z),

3.40

according to which

\begin{aligned} (Δ^{2} c) (k) := & (Δ (Δ c)) (k) = c (k) - 2 c (k - 1) + c (k - 2), k \in Z, \\ c = {c (k)} \in ℓ (Z) . \end{aligned}

Observe in particular that

c \in ℓ^{\infty} (Z) \Rightarrow Δ c \in ℓ^{\infty} (Z), w i t h ‖ Δ c ‖_{\infty} \leq 2 ‖ c ‖_{\infty}, c \in ℓ^{\infty} (Z) .

3.42

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

Lemma 3.1

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

\begin{aligned} c (j + k) - 2 c (j) + c (j - k) = \\ = \sum_{ℓ = 1}^{k - 1} ℓ (Δ^{2} c) (j + k - ℓ + 1) + \sum_{ℓ = 1}^{k} ℓ (Δ^{2} c) (j - k + ℓ + 1), j \in Z . \end{aligned}

Proof â–¼

Let

k \in N

, and apply 3.41 to deduce that, for any

j \in Z

\begin{aligned} \sum_{ℓ = 1}^{k} ℓ (Δ^{2} c) (j - k + ℓ + 1) = \\ = \sum_{ℓ = 1}^{k} ℓ {c (j - k + ℓ + 1) - 2 c (j - k + ℓ) + c (j - k + ℓ - 1)} \\ = \sum_{ℓ = 2}^{k + 1} (ℓ - 1) c (j - k + ℓ) - 2 \sum_{ℓ = 1}^{k} ℓ c (j - k + ℓ) + \sum_{ℓ = 0}^{k - 1} (ℓ + 1) c (j - k + ℓ) \\ = \sum_{ℓ = 1}^{k} {(ℓ - 1) - 2 ℓ + (ℓ + 1)} c (j - k + ℓ) + k c (j + 1) + {c (j - k) - (k + 1) c (j)} \\ = c (j - k) - c (j) + k {c (j + 1) - c (j)}, \end{aligned}

and similarly, for $k \geq 2$ ,

\begin{aligned} \sum_{ℓ = 1}^{k - 1} ℓ (Δ^{2} c) (j + k - ℓ + 1) = \\ = \sum_{ℓ = 1}^{k - 1} ℓ {c (j + k - ℓ + 1) - 2 c (j + k - ℓ) + c (j + k - ℓ - 1)} \\ = \sum_{ℓ = 0}^{k - 2} (ℓ + 1) c (j + k - ℓ) - 2 \sum_{ℓ = 1}^{k - 1} ℓ c (j + k - ℓ) + \sum_{ℓ = 2}^{k} (ℓ - 1) c (j + k - ℓ) \end{aligned}

\begin{aligned} = \sum_{ℓ = 1}^{k - 1} {(ℓ + 1) - 2 ℓ + (ℓ - 1)} c (j + k - ℓ) + {c (j + k) - k c (j + 1)} + (k - 1) c (j) \\ = c (j + k) - c (j) + k {c (j) - c (j + 1)} . \end{aligned}

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 ]

(x + t)^{m - 1} = \sum_{k} g_{m} (k + t) N_{m} (x - k), x, t \in R,

3.44

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

g_{m} (x) := \prod_{j = 1}^{m - 1} (x + j), x \in R,

3.45

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

Lemma 3.2

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

\sum_{k = 1}^{m - 1} k^{2} ϕ_{m} (k) = \frac{m}{24}, i f m i s e v e n, m \geq 4;

3.46

and

\sum_{k = 1}^{m} ϕ_{m} (k) = \frac{1}{2}, i f m i s o d d .

3.47

Proof â–¼

First we differentiate the identity 3.44 repeatedly with respect to

t

, before setting

t = 0

, to obtain the identities

x^{ℓ} = \frac{ℓ!}{(m - 1)!} \sum_{k} g_{m}^{(m - 1 - ℓ)} (k) N_{m} (x - k), x \in R, ℓ = 0, 1, \dots, m - 1.

3.48

Now observe from 3.45 that

g_{m} (x) = x^{m - 1} + \sum_{j = 0}^{m - 2} α_{m} (j) x^{j}, x \in R,

3.49

where

α_{m} (m - 2) = 1 + 2 + \dots + (m - 1) = \frac{(m - 1) m}{2},

3.50

and

\begin{aligned} α_{m} (m - 3) & = 1 [2 + \dots + (m - 1)] + 2 [3 + \dots + (m - 1)] + \dots + (m - 2) (m - 1) \\ = \sum_{j = 1}^{m - 2} j [\frac{(m - 1) m}{2} - \frac{j (j + 1)}{2}] = \frac{(m - 1) m}{2} \sum_{j = 1}^{m - 2} j - \frac{1}{2} (\sum_{j = 1}^{m - 2} j^{3} + \sum_{j = 1}^{m - 2} j^{2}) \end{aligned}

\begin{aligned} = \frac{1}{4} (m - 2) (m - 1)^{2} m - \frac{1}{2} [\frac{(m - 2)^{2} (m - 1)^{2}}{4} + \frac{(m - 2) (m - 1) (2 m - 3)}{6}] \\ = \frac{m (m - 1) (m - 2) (3 m - 1)}{24} . \end{aligned}

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

g_{m}^{(m - 2)} (x) = (m - 1)! x + (m - 2)! α_{m} (m - 2) = (m - 1)! x + \frac{1}{2} m!;

3.51

and

\begin{aligned} g_{m}^{(m - 3)} (x) & = \frac{(m - 1)!}{2} x^{2} + (m - 2)! α_{m} (m - 2) x + (m - 3)! α_{m} (m - 3) \\ = \frac{(m - 1)!}{2} x^{2} + \frac{m!}{2} x + \frac{m! (3 m - 1)}{24} . \end{aligned}

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

\begin{aligned} x = & \sum_{k} (k + \frac{m}{2}) N_{m} (x - k), x \in R; \\ x^{2} = & \sum_{k} [k^{2} + m k + \frac{m (3 m - 1)}{12}] N_{m} (x - k), x \in R . \end{aligned}

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

\sum_{k} N_{m} (k) = 1,

3.55

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

\sum_{k} k N_{m} (k) = \frac{m}{2} .

3.56

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

0 = \sum_{k} k^{2} N_{m} (k) - m (\frac{m}{2}) + \frac{m (3 m - 1)}{12},

which yields

\sum_{k} k^{2} N_{m} (k) = \frac{m (3 m + 1)}{12} .

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{array}{r} \sum_{k} k^{2} ϕ_{2 n} (k) = \sum_{k} k^{2} N_{2 n} (k + n) = \sum_{k} (k - n)^{2} N_{2 n} (k) = \frac{2 n (6 n + 1)}{12} - 2 n^{2} + n^{2} = \frac{n}{6}, \end{array}

that is,

\sum_{k} k^{2} ϕ_{2 n} (k) = \frac{n}{6}, n = 2, 3, \dots .

3.58

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

\begin{aligned} s u p p ϕ_{2 n} = & [- n, n] \cap Z, w i t h ϕ_{2 n} (- n) = ϕ_{2 n} (n) = 0; \\ s u p p ϕ_{2 n + 1} = & [- n, n + 1] \cap Z, w i t h ϕ_{2 n + 1} (- n) = ϕ_{2 n + 1} (n + 1) = 0. \end{aligned}

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

\begin{array}{r} \frac{n}{6} = \sum_{k = - n + 1}^{n - 1} k^{2} ϕ_{2 n} (k) = \sum_{k = - n + 1}^{- 1} k^{2} ϕ_{2 n} (- k) + \sum_{k = 1}^{n - 1} k^{2} ϕ_{2 n} (k) = 2 \sum_{k = 1}^{n - 1} k^{2} ϕ_{2 n} (k), \end{array}

which yields the desired result 3.46.

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

\begin{array}{r} 1 = \sum_{k} ϕ_{2 n + 1} (k) = \sum_{k = - n + 1}^{0} ϕ_{2 n + 1} (1 - k) + \sum_{k = 1}^{n} ϕ_{2 n + 1} (k) = 2 \sum_{k = 1}^{n} ϕ_{2 n + 1} (k), \end{array}

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 $c = {c (k)} \in ℓ (Z)$ , we now define the subdivision sequences ${c_{m, d}^{[r]}} \in ℓ (Z)$ , $r = 0, 1, \dots$ , recursively by means of the iterative scheme

c_{m, d}^{[0]} := c; c_{m, d}^{[r + 1]} := S_{m, d} c_{m, d}^{[r]} = S_{m, d}^{r} c, r = 0, 1, \dots,

3.61

with $S_{m, d} : ℓ (Z) \to ℓ (Z)$ denoting the $m^{t h}$ order cardinal spline subdivision operator given by

(S_{m, d} c) (j) := \sum_{k} p_{m, d} (j - d k) c (k), j \in Z, c = {c (k)} \in ℓ (Z),

3.62

where ${p_{m, d} (k)} \in ℓ_{0} (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 $c$ is bounded, the difference between the values of the function $Φ_{c, m}$ in 3.38 at the (dense in $R$ ) $d$ -adic point set ${\frac{j}{d^{r}} : j \in Z, r = 0, 1, \dots}$ and the subdivision sequence values ${c_{m, d}^{[r]} (j) : j \in Z, r = 0, 1, \dots}$ is bounded as follows in terms of backward differences of the sequences $c^{[r]}$ .

Theorem 3.1

For any integer $m \geq 2$ , and a given control point sequence $c = {c (k)} \in ℓ^{\infty} (Z)$ , let the function $Φ_{c, m} : R \to R$ be defined by 3.38 in terms of the $m^{t h}$ order centered cardinal $B$ -spline $ϕ_{m}$ , as given in 2.2. Then, for any integers $d \geq 2$ and $r \in {0, 1, \dots}$ , the subdivision sequence $c_{m, d}^{[r]}$ , as defined recursively in 3.61, 3.62, satisfies

\begin{aligned} Φ_{c, 2} (\frac{j}{d^{r}}) - c_{2, d}^{[r]} (j) = & 0, j \in Z; \\ sup_{j} | Φ_{c, m} (\frac{j}{d^{r}}) - c_{m, d}^{[r]} (j) | \leq & {\begin{cases} (m - 2) ‖ Δ c_{m, d}^{[r]} ‖_{\infty}, & m o d d; \\ \frac{m}{24} ‖ Δ^{2} c_{m, d}^{[r]} ‖_{\infty}, & m e v e n, m \geq 4. \end{cases} \end{aligned}

Proof â–¼

First, for any fixed

r \in {0, 1, \dots}

, we apply the refinability property 2.18 of

ϕ_{m}

to deduce from 3.38, together with 3.61, 3.62, that, for any

x \in R

\begin{aligned} Φ_{c, m} (x) & = \sum_{k} c_{m, d}^{[0]} (k) ϕ_{m} (x - k) \\ = \sum_{k} c_{m, d}^{[0]} (k) {\sum_{ℓ} p_{m, d} (ℓ) ϕ_{m} (d x - d k - ℓ)} \\ = \sum_{k} c_{m, d}^{[0]} (k) {\sum_{ℓ} p_{m, d} (ℓ - d k) ϕ_{m} (d x - ℓ)} \\ = \sum_{ℓ} {\sum_{k} p_{m, d} (ℓ - d k) c_{m, d}^{[0]} (k)} ϕ_{m} (d x - ℓ) = \\ = \sum_{ℓ} c_{m, d}^{[1]} (ℓ) ϕ_{m} (d x - ℓ) = \dots = \sum_{ℓ} c_{m, d}^{[r]} (ℓ) ϕ_{m} (d^{r} x - ℓ), \end{aligned}

that is,

Φ_{c, m} (x) = \sum_{k} c_{m, d}^{[r]} (k) ϕ_{m} (d^{r} x - k), x \in R,

3.61

and thus

Φ_{c, m} (\frac{j}{d^{r}}) = \sum_{k} c_{m, d}^{[r]} (k) ϕ_{m} (j - k) = \sum_{k} c_{m, d}^{[r]} (j - k) ϕ_{m} (k), j \in Z .

3.62

By applying 2.9, we deduce from 3.62 that

Φ_{c, m} (\frac{j}{d^{r}}) - c_{m, d}^{[r]} (j) = \sum_{k} {c_{m, d}^{[r]} (j - k) - c_{m, d}^{[r]} (j)} ϕ_{m} (k), j \in Z,

3.63

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

ϕ_{2} (k) = δ (k), k \in Z,

3.64

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

Suppose next that $m = 2 n + 1$ for some $n \in 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

ϕ_{m} (x) \geq 0, x \in R,

3.65

that, for any $j \in Z$ ,

\begin{aligned} | Φ_{c, 2 n + 1} (\frac{j}{d^{r}}) - c_{2 n + 1, d}^{[r]} (j) | & = | \sum_{k = - n + 1}^{n} {c_{2 n + 1, d}^{[r]} (j - k) - c_{2 n + 1, d}^{[r]} (j)} ϕ_{2 n + 1} (k) | \end{aligned}

\begin{aligned} = | \sum_{k = 1}^{n - 1} {c_{2 n + 1, d}^{[r]} (j + k) - c_{2 n + 1, d}^{[r]} (j)} ϕ_{2 n + 1} (- k) \\ - \sum_{k = 1}^{n} {c_{2 n + 1, d}^{[r]} (j) - c_{2 n + 1, d}^{[r]} (j - k)} ϕ_{2 n + 1} (k) | \\ = | \sum_{k = 1}^{n - 1} {\sum_{ℓ = j + 1}^{j + k} (Δ c_{2 n + 1, d}^{[r]}) (ℓ)} ϕ_{2 n + 1} (- k) \\ - \sum_{k = 1}^{n} {\sum_{ℓ = j - k + 1}^{j} (Δ c_{2 n + 1, d}^{[r]}) (ℓ)} ϕ_{2 n + 1} (k) | \\ \leq ‖ Δ c_{2 n + 1, d}^{[r]} ‖_{\infty} {\sum_{k = 1}^{n - 1} k ϕ_{2 n + 1} (- k) + \sum_{k = 1}^{n} k ϕ_{2 n + 1} (k)} \end{aligned}

Now observe from the symmetry property 2.11 that

\begin{aligned} \sum_{k = 1}^{n - 1} k ϕ_{2 n + 1} (- k) & = \sum_{k = 1}^{n - 1} k ϕ_{2 n + 1} (1 + k) = \sum_{k = 2}^{n} (k - 1) ϕ_{2 n + 1} (k) = \sum_{k = 1}^{n} (k - 1) ϕ_{2 n + 1} (k), \end{aligned}

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

\begin{aligned} | Φ_{c, 2 n + 1} (\frac{j}{d^{r}}) - c_{2 n + 1, d}^{[r]} (j) | & \leq ‖ Δ c_{2 n + 1, d}^{[r]} ‖_{\infty} \sum_{k = 1}^{n} (2 k - 1) ϕ_{2 n + 1} (k) \\ \leq (2 n - 1) ‖ Δ c_{2 n + 1, d}^{[r]} ‖_{\infty} \sum_{k = 1}^{n} ϕ_{2 n + 1} (k) \\ = (n - \frac{1}{2}) ‖ Δ c_{2 n + 1, d}^{[r]} ‖_{\infty}, \end{aligned}

and thereby implying the first line of 3.64.

Suppose next that $m = 2 n$ 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 Z$ ,

\begin{aligned} Φ_{c, 2 n} (\frac{j}{d^{r}}) - c_{2 n, d}^{[r]} (j) = \\ = \sum_{k = - n + 1}^{n - 1} {c_{2 n, d}^{[r]} (j - k) - c_{2 n, d}^{[r]} (j)} ϕ_{2 n} (k) \\ = \sum_{k = 1}^{n - 1} {c_{2 n, d}^{[r]} (j + k) - c_{2 n, d}^{[r]} (j)} ϕ_{2 n} (- k) - \sum_{k = 1}^{n - 1} {c_{2 n, d}^{[r]} (j) - c_{2 n, d}^{[r]} (j - k)} ϕ_{2 n} (k) \\ = \sum_{k = 1}^{n - 1} {c_{2 n, d}^{[r]} (j + k) - 2 c_{2 n, d}^{[r]} (j) + c_{2 n, d}^{[r]} (j - k)} ϕ_{2 n} (k) . \end{aligned}

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

\begin{aligned} Φ_{c, 2 n} (\frac{j}{d^{r}}) - c_{2 n, d}^{[r]} (j) = \\ = \sum_{k = 1}^{n - 1} {\sum_{ℓ = 1}^{k - 1} ℓ △^{2} c_{2 n, d}^{[r]} (j + k - ℓ + 1) + \sum_{ℓ = 1}^{k} ℓ △^{2} c_{2 n, d}^{[r]} (j - k + ℓ + 1)} ϕ_{2 n} (k), \end{aligned}

and thus, by using also 3.65,

\begin{aligned} | Φ_{c, 2 n} (\frac{j}{d^{r}}) - c_{2 n, d}^{[r]} (j) | & \leq ‖ △^{2} c_{2 n, d}^{[r]} ‖_{\infty} \sum_{k = 1}^{n - 1} {\sum_{ℓ = 1}^{k - 1} ℓ + \sum_{ℓ = 1}^{k} ℓ} ϕ_{2 n} (k) \\ = ‖ △^{2} c_{2 n, d}^{[r]} ‖_{\infty} \sum_{ℓ = 1}^{k - 1} {\frac{(k - 1) k}{2} + \frac{k (k + 1)}{2}} ϕ_{2 n} (k) \\ = ‖ △^{2} c_{2 n, d}^{[r]} ‖_{\infty} \sum_{k = 1}^{n - 1} k^{2} ϕ_{2 n} (k) = \frac{n}{12} ‖ △^{2} c_{2 n, d}^{[r]} ‖_{\infty}, \end{aligned}

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 ${‖ △ c_{m, d}^{[r]} ‖_{\infty} : r = 0, 1, \dots}$ and ${‖ △^{2} c_{m, d}^{[r]} ‖_{\infty} : r = 0, 1, \dots}$ , as appearing in the upper bounds 3.64, converge geometrically to zero for $r \to \infty$ , as follows.

Theorem 3.2

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

\begin{aligned} ‖ △ c_{m, d}^{[r]} ‖_{\infty} \leq & ‖ △ c ‖_{\infty} (\frac{1}{d})^{r}, r = 0, 1, \dots; \\ ‖ △^{2} c_{m, d}^{[r]} ‖_{\infty} \leq & ‖ △^{2} c ‖_{\infty} (\frac{1}{d^{2}})^{r}, r = 0, 1, \dots, \end{aligned}

are satisfied.

Proof â–¼

For any integer

r \in 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 Z

\begin{aligned} (△ c_{m, d}^{[r]}) (j) & = c_{m, d}^{[r]} (j) - c_{m, d}^{[r]} (j - 1) \\ = \sum_{k} {p_{m, d} (j - d k) - p_{m, d} (j - 1 - d k)} c_{m, d}^{[r - 1]} (k) \\ = \frac{1}{d} \sum_{k} \sum_{ℓ = 0}^{d - 1} {p_{m - 1, d} (j - d k + (d - 1) μ_{m - 1} - ℓ) - \\ - p_{m - 1, d} (j - d k + (d - 1) μ_{m - 1} - 1 - ℓ)} c_{m, d}^{[r - 1]} (k) \\ = \frac{1}{d} \sum_{k} {p_{m - 1, d} (j - d k + (d - 1) μ_{m - 1}) \end{aligned}

\begin{aligned} - p_{m - 1, d} (j - d (k + 1) + (d - 1) μ_{m - 1})} c_{m, d}^{[r - 1]} (k) \\ = \frac{1}{d} {\sum_{k} p_{m - 1, d} (j + (d - 1) μ_{m - 1} - d k) c_{m, d}^{[r - 1]} (k) \\ - \sum_{k} p_{m - 1, d} (j + (d - 1) μ_{m - 1} - d k) c_{m, d}^{[r - 1]} (k - 1)} \\ = \frac{1}{d} \sum_{k} p_{m - 1, d} (j + (d - 1) μ_{m - 1} - d k) (△ c_{m, d}^{[r - 1]}) (k), \end{aligned}

that is,

(△ c_{m, d}^{[r]}) (j) = \frac{1}{d} \sum_{k} p_{m - 1, d} (j + (d - 1) μ_{m - 1} - d k) (△ c_{m, d}^{[r - 1]}) (k), j \in Z .

3.59

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

then yields

\begin{aligned} (△^{2} c_{m, d}^{[r]}) (j) = \\ = \frac{1}{d^{2}} \sum_{k} p_{m - 2, d} (j + (d - 1) (μ_{m - 1} + μ_{m - 2}) - d k) (△^{2} c_{m, d}^{[r - 1]}) (k), j \in Z . \end{aligned}

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

(△^{2} c_{m, d}^{[r]}) (j) = \frac{1}{d^{2}} \sum_{k} p_{m - 2, d} (j + d - 1 - d k) (△^{2} c_{m, d}^{[r - 1]}) (k), j \in Z .

3.61

According to 2.19, 2.20, we have

p_{m, d} (k) \geq 0,, k \in Z .

3.62

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

\begin{aligned} | (△ c_{m, d}^{[r]}) (j) | \leq & ‖ △ c_{m, d}^{[r - 1]} ‖_{\infty} \frac{1}{d} \sum_{k} p_{m - 1, d} (j + (d - 1) μ_{m} - d k), j \in Z, \\ | (△^{2} c_{m, d}^{[r]}) (j) | \leq & ‖ △^{2} c_{m, d}^{[r - 1]} ‖_{\infty} \frac{1}{d^{2}} \sum_{k} p_{m - 2, d} (j + d - 1 - d k), j \in Z, \end{aligned}

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

\begin{array}{r} | (△ c_{m, d}^{[r]}) (j) | \leq \frac{1}{d} ‖ △ c_{m, d}^{[r - 1]} ‖_{\infty}; j \in Z, \\ | (△^{2} c_{m, d}^{[r]}) (j) | \leq \frac{1}{d^{2}} ‖ △^{2} c_{m, d}^{[r - 1]} ‖_{\infty}, j \in Z, \end{array}

from which we deduce that

\begin{aligned} ‖ (△ c_{m, d}^{[r]}) ‖_{\infty} \leq & \frac{1}{d} ‖ △ c_{m, d}^{[r - 1]} ‖_{\infty}, r = 1, 2, \dots; \\ ‖ (△^{2} c_{m, d}^{[r]}) ‖_{\infty} \leq & \frac{1}{d^{2}} ‖ △^{2} c_{m, d}^{[r - 1]} ‖_{\infty}, r = 1, 2, \dots . \end{aligned}

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

‖ △ c_{m, d}^{[r]} ‖_{\infty} \leq \frac{1}{d} (\frac{1}{d} ‖ △ c_{m, d}^{[r - 2]} ‖_{\infty}) \leq \dots \leq (\frac{1}{d})^{r} ‖ △ c_{m, d}^{[0]} ‖_{\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^{t h}$ order cardinal spline subdivision operator $S_{m, d} : ℓ (Z) \to ℓ (Z)$ , as defined by 3.62 in terms of the refinement sequence ${p_{m, d} (k)} \in ℓ_{0} (Z)$ of Theorem 2.1, provides, for any given control point sequence $c = {c (k)} \in ℓ^{\infty} (Z)$ , a convergent subdivision scheme 3.61, where the recursively generated subdivision sequences $c_{m, d}^{[r]} = {c_{m, d}^{[r]} (k)} \in ℓ^{\infty} (Z)$ , $r = 0, 1, \dots$ , satisfy

\begin{array}{r} Φ_{c, 2} (\frac{j}{d^{r}}) - c_{2, d}^{[r]} (j) = 0, j \in Z, \end{array}

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

sup_{j} | Φ_{c, m} (\frac{j}{d^{r}}) - c_{m, d}^{[r]} (j) | \leq {\begin{cases} \frac{m - 2}{2} ‖ △ c_{m, d}^{[r]} ‖_{\infty} (\frac{1}{d})^{r}, & m o d d; \\ \frac{m}{24} ‖ △^{2} c_{m, d}^{[r]} ‖_{\infty} (\frac{1}{d^{2}})^{r}, & m e v e n, m \geq 4; \end{cases} r = 0, 1, \dots

3.66

with $Φ_{c, m} : R \to 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 $Φ_{c, 2}$ is the (continuous) piecewise linear interpolant such that

Φ_{c, 2} (j) = c (j), j \in Z .

3.67

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

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

\frac{j_{r}}{d^{r}} \to x, r \to \infty .

3.68

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

c_{m, d}^{[r]} (j_{r}) \to Φ_{c, m} (x), r \to \infty,

3.69

according to which the co-ordinate sequences ${(\frac{j}{d^{r}}, c_{m, d}^{[r]} (j)) : j \in Z}$ , $r = 0, 1, \dots$ , do indeed converge to the graph of the cardinal spline $Φ_{c, m}$ as $r \to \infty$ .

$c \in ℓ (Z)$ , if $m = 2$ ;
$Δ c \in ℓ^{\infty} (Z)$ , if $m$ is odd;
$Δ^{2} c \in ℓ^{\infty} (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$ ,

sup_{j} | Φ_{c, m} (\frac{j}{d^{r}}) - c_{m, d}^{[r]} (j) | \leq {\begin{cases} (m - 2) ‖ c ‖_{\infty} (\frac{1}{d})^{r}, & i f m i s o d d; \\ \frac{m ‖ c ‖_{\infty}}{6} (\frac{1}{d^{2}})^{r}, & i f m i s e v e n, \end{cases} r = 0, 1, \dots

3.70

Next, we observe from the definition 3.62 of the $d$ -ary cardinal spline subdivision operator $S_{m, d} : ℓ (Z) \to ℓ (Z)$ that, for any sequence $c = {c (k)} \in ℓ (Z)$ and integers $j \in Z$ , $ℓ \in {0, \dots, d - 1}$ ,

(S_{m, d} c) (d j + ℓ) = \sum_{k} p_{m, d} (d (j - k) + ℓ) c (k) = \sum_{k} p_{m, d} (d k + ℓ) c (j - k),

and thus

\begin{aligned} (S_{m, d} c) (d j + ℓ) = \sum_{k} w_{m, d}^{[ℓ]} (k) c (j - k), \end{aligned}

$j \in Z; ℓ = 0, \dots, d - 1; c = {c (k)} \in ℓ (Z)$ , with ${w_{m, d}^{[ℓ]} (k)} \in ℓ_{0} (Z)$ denoting the weight sequences defined by

w_{m, d}^{[ℓ]} (k) := p_{m, d} (d k + ℓ), k \in Z; ℓ = 0, \dots, d - 1.

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 $c = {c (k)} \in ℓ (Z)$ , by

\begin{aligned} c_{m, d}^{[0]} := c; \\ c_{m, d}^{[r + 1]} (d j + ℓ) = \sum_{k} w_{m, d}^{[ℓ]} (k) c_{m, d}^{[r]} (j - k), j \in Z; ℓ = 0, \dots, d - 1; r = 0, 1, \dots; \end{aligned}

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

\begin{aligned} s u p p {w_{m, d}^{[ℓ]} (k)} = [- ⌊ \frac{(d - 1) ⌊ \frac{m}{2} ⌋ + ℓ}{d} ⌋, ⌊ \frac{(d - 1) ⌊ \frac{m + 1}{2} ⌋ - ℓ}{d} ⌋] \cap Z, ℓ = 0, \dots, d - 1. \end{aligned}

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

\begin{aligned} {w_{m, d}^{[ℓ]} (k) : k = ⌈ \frac{- (d - 1) ⌊ \frac{m}{2} ⌋ - ℓ}{d} ⌉, \dots, ⌊ \frac{(d - 1) ⌊ \frac{m + 1}{2} ⌋ - ℓ}{d} ⌋}, \end{aligned}

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

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

Table 3. The weight sequences

{w_{m, 2}^{[ℓ]} (k)}

$m$

$\begin{matrix} ℓ = 0, \end{matrix}$

ℓ=1,

ℓ=2

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

None

The weight sequences

{w_{m, 3}^{[ℓ]} (k)}

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

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

Table 3. The weight sequences

{w_{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 Z$ , the “old" point $c^{[r]} (j)$ is replaced by the altogether $d$ “new" (or updated) points ${c_{m, d}^{[r + 1]} (d j + ℓ) : ℓ = 0, \dots, d - 1}$ . 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 $c \in ℓ^{\infty} (Z)$ in Corollary 3.1 be chosen as $c = \bm @ g e n e r a l \boldmath \m @ n e \mv @ b o l d \bm @ c o m m a n d δ = {δ (k)} \in ℓ_{0} (Z)$ , the Kronecker delta sequence, for which 3.40 and 3.41 imply

‖ Δ \bm @ g e n e r a l \boldmath \m @ n e \mv @ b o l d \bm @ c o m m a n d δ ‖_{\infty} = 1; ‖ Δ^{2} \bm @ g e n e r a l \boldmath \m @ n e \mv @ b o l d \bm @ c o m m a n d δ ‖_{\infty} = 2.

4.75

Also, from 3.38, we have

Φ_{\bm @ g e n e r a l \boldmath \m @ n e \mv @ b o l d \bm @ c o m m a n d δ, m} = ϕ_{m} .

4.76

If follows from Corollary 3.1 that, for the control point sequence choice $c = \bm @ g e n e r a l \boldmath \m @ n e \mv @ b o l d \bm @ c o m m a n d δ$ , the subdivision scheme 3.61, 3.62 renders the graph of the centered cardinal B-spline $ϕ_{m}$ , with in particular, for $m \geq 3$ , from 3.66 and 4.75, geometric convergence rates

sup_{j} | ϕ_{m} (\frac{j}{d^{r}}) - c_{m, d}^{[r]} (j) | \leq {\begin{cases} \frac{m - 2}{2} (\frac{1}{d})^{r}, & i f m i s o d d; \\ \frac{m}{12} (\frac{1}{d^{2}})^{r}, & i f m i s e v e n, \end{cases} r = 0, 1, \dots

4.77

As noted before in the more general setting of Remark 3.1 (b), the graph of $ϕ_{m}$ is rendered by plotting the co-ordinate sequence ${(\frac{j}{d^{r}}, c_{m, d}^{[r]} (j)) : j \in Z}$ 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 ${c_{m, d}^{[r]} (k)} \in ℓ (Z)$ , $r = 1, 2, \dots,$ as generated iteratively by the cardinal spline $d$ -ary subdivision scheme 3.61, 3.62, with control point sequence $c = {c (k)} = {δ (k)} \in ℓ_{0} (Z)$ , satisfy the alternative recursion formulation

\begin{aligned} c_{m, d}^{[1]} (j) = & p_{m, d} (j), j \in Z; \\ c_{m, d}^{[r + 1]} (j) = & \sum_{k} p_{m, d} (k) c_{m, d}^{[r]} (j - d^{r} k), j \in Z; r = 1, 2, \dots . \end{aligned}

Moreover, ${c_{m, d}^{[r]} (k)} \in ℓ_{0} (Z)$ , $r = 1, 2, \dots$ , where

\begin{aligned} c_{m, d}^{[r]} (- (d^{r} - 1) ⌊ \frac{m}{2} ⌋) = & (p_{m, d} (- (d - 1) ⌊ \frac{m}{2} ⌋))^{r}, r = 1, 2, \dots \end{aligned}

\begin{aligned} c_{m, d}^{[r]} ((d^{r} - 1) ⌊ \frac{m + 1}{2} ⌋) = & {(p_{m, d} ((d - 1) ⌊ \frac{m + 1}{2} ⌋))}^{r}, r = 1, 2, \dots \end{aligned}

and with support

s u p p {c_{m, d}^{[r]} (j)} = [- (d^{r} - 1) ⌊ \frac{m}{2} ⌋, (d^{r} - 1) ⌊ \frac{m + 1}{2} ⌋] \cap Z, r = 1, 2, \dots

4.81

Proof â–¼

First, observe that 4.78 is obtained by setting $c = {c (k)} = {δ (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_{m, d}^{[2]} (j) = \sum_{k} p_{m, d} (j - d k) p_{m, d} (k), j \in 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 N$ . By also applying 3.61, 3.62, we deduce that, for any $j \in Z$ ,

\begin{aligned} c_{m, d}^{[r + 2]} (j) & = \sum_{k} p_{m, d} (j - d k) c_{m, d}^{[r + 1]} (k) \\ = \sum_{k} p_{m, d} (j - d k) {\sum_{ℓ} p_{m, d} (ℓ) c_{m, d}^{[r]} (k - d^{r} ℓ)} \\ = \sum_{ℓ} p_{m, d} (ℓ) {\sum_{k} p_{m, d} (j - d k) c_{m, d}^{[r]} (k - d^{r} ℓ)} \\ = \sum_{ℓ} p_{m, d} (ℓ) {\sum_{k} p_{m, d} (j - d^{r + 1} ℓ - d k) c_{m, d}^{[r]} (k)} \\ = \sum_{ℓ} p_{m, d} (ℓ) c_{m, d}^{[r + 1]} (j - d^{r + 1} ℓ), \end{aligned}

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 N$ ,

c_{m, d}^{[r]} (j) = 0, j \in Z ∖ {- (d^{r} - 1) ⌊ \frac{m}{2} ⌋, \dots, (d^{r} - 1) ⌊ \frac{m + 1}{2} ⌋} .

4.78

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

c_{m, d}^{[r + 1]} (j) = \sum_{k = - (d - 1) ⌊ \frac{m}{2} ⌋}^{(d - 1) ⌊ \frac{m + 1}{2} ⌋} p_{m, d} (k) c_{m, d}^{[r]} (j - d^{r} k), j \in Z .

4.79

Since

j - d^{r} k < - (d^{r} - 1) ⌊ \frac{m}{2} ⌋, k = - (d - 1) ⌊ \frac{m}{2} ⌋, \dots, (d - 1) ⌊ \frac{m + 1}{2} ⌋,

if and only if

j < d^{r} (- (d - 1) ⌊ \frac{m}{2} ⌋) - (d^{r} - 1) ⌊ \frac{m}{2} ⌋ = - (d^{r + 1} - 1) ⌊ \frac{m}{2} ⌋,

whereas

j - d^{r} k > (d^{r} - 1) ⌊ \frac{m + 1}{2} ⌋, k = - (d - 1) ⌊ \frac{m}{2} ⌋, \dots, (d - 1) ⌊ \frac{m + 1}{2} ⌋,

if and only if

j > d^{r} ((d - 1) ⌊ \frac{m + 1}{2} ⌋) + (d^{r} - 1) ⌊ \frac{m + 1}{2} ⌋ = (d^{r + 1} - 1) ⌊ \frac{m + 1}{2} ⌋,

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 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 N$ be fixed, and apply 4.79 to obtain

\begin{array}{llll} c_{m, d}^{[r + 1]} (- (d^{r + 1} - 1) ⌊ \frac{m}{2} ⌋) = \sum_{k = - (d - 1) ⌊ \frac{m}{2} ⌋}^{(d - 1) ⌊ \frac{m + 1}{2} ⌋} p_{m, d} (k) c_{m, d}^{[r]} (- (d^{r + 1} - 1) ⌊ \frac{m}{2} ⌋ - d^{r} k); \\ c_{m, d}^{[r + 1]} ((d^{r + 1} - 1) ⌊ \frac{m + 1}{2} ⌋) = \sum_{k = - (d - 1) ⌊ \frac{m}{2} ⌋}^{(d - 1) ⌊ \frac{m + 1}{2} ⌋} p_{m, d} (k) c_{m, d}^{[r]} ((d^{r + 1} - 1) ⌊ \frac{m + 1}{2} ⌋ - d^{r} k) . \end{array}

4.80

Since, moreover,

\begin{aligned} - (d^{r + 1} - 1) ⌊ \frac{m}{2} ⌋ - d^{r} k \geq & - (d^{r} - 1) ⌊ \frac{m}{2} ⌋ \Leftrightarrow k \leq - (d - 1) ⌊ \frac{m}{2} ⌋; \\ (d^{r + 1} - 1) ⌊ \frac{m + 1}{2} ⌋ - d^{r} k \leq & (d^{r} - 1) ⌊ \frac{m + 1}{2} ⌋ \Leftrightarrow k \geq (d - 1) ⌊ \frac{m + 1}{2} ⌋, \end{aligned}

if follows from 4.80 and 4.78 that

\begin{aligned} c_{m, d}^{[r + 1]} (- (d^{r + 1} - 1) ⌊ \frac{m}{2} ⌋) = & p_{m, d} (- (d - 1) ⌊ \frac{m}{2} ⌋) c_{m, d}^{[r]} (- (d^{r} - 1) ⌊ \frac{m}{2} ⌋); \\ c_{m, d}^{[r + 1]} ((d^{r + 1} - 1) ⌊ \frac{m + 1}{2} ⌋) = & p_{m, d} ((d - 1) ⌊ \frac{m + 1}{2} ⌋) c_{m, d}^{[r]} ((d^{r} - 1) ⌊ \frac{m + 1}{2} ⌋), \end{aligned}

from which 4.80 then follows inductively.

Proof â–¼

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

{(\frac{j}{d^{r}}, c_{m, d}^{[r]} (j)) : j = - (d^{r} - 1) ⌊ \frac{m}{2} ⌋, \dots, (d^{r} - 1) ⌊ \frac{m + 1}{2} ⌋},

4.81

as computed recursively by means of

\begin{aligned} c_{m, d}^{[1]} (j) = & p_{m, d} (j), j = - (d - 1) ⌊ \frac{m}{2} ⌋, \dots, (d - 1) ⌊ \frac{m + 1}{2} ⌋; \\ c_{m, d}^{[r + 1]} (j) = & \sum_{k = μ_{m, d} (r)}^{ν_{m, d} (r)} p_{m, d} (k) c_{m, d}^{[r]} (j - d^{r} k), \\ j = - (d^{r + 1} - 1) ⌊ \frac{m}{2} ⌋, \dots, (d^{r + 1} - 1) ⌊ \frac{m + 1}{2} ⌋; r = 1, 2, \dots, \end{aligned}

where

\begin{aligned} μ_{m, d} (r) := & max {- (d - 1) ⌊ \frac{m}{2} ⌋, - ⌊ {(d^{r} - 1) ⌊ \frac{m + 1}{2} ⌋ - j} / d^{r} ⌋}; \\ ν_{m, d} (r) := & min {(d - 1) ⌊ \frac{m + 1}{2} ⌋, ⌊ {(d^{r} - 1) ⌊ \frac{m}{2} ⌋ + j} / d^{r} ⌋} . \end{aligned}

For a sufficiently large $r \in N$ , the coordinate points 4.81 then render the graph of the centered cardinal B-Spline $ϕ_{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_{3, 2}^{[r]}}$ for rendering the graph of $ϕ_{3}$ .

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

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

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

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

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

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

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

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

\includegraphics[width=\textwidth ]{./figures1/4phid4r=2.jpg} — Figure 4. The subdivision points ${c_{4, 4}^{[r]}}$ for rendering the graph of $ϕ_{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 ${c (0), \dots, c (M)} \subset R^{s}$ , for $M \geq 2$ , where $s = 2$ or $s = 3$ , and with $c (0) \neq c (M)$ , we define the extended control point set $c = {c (k) : k \in Z} \subset R^{s}$ by means of periodicity, that is,

c (j + M + 1) = c (j), j \in Z,

5.86

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

Φ_{c, m} (x) := \sum_{k} c (k) ϕ_{m} (x - k), x \in R,

5.87

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

c_{m, d}^{[0]} := c; c_{m, d}^{[r + 1]} (d j + ℓ) = \sum_{k} w_{m, d}^{[ℓ]} (k) c_{m, d}^{[r]} (j - k),

5.88

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

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

Theorem 5.1

Let $c = {c (k) : k \in Z} \in 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^{t h}$ order cardinal spline subdivision sequences ${c_{m, d}^{[r]} : r = 0, 1 \dots,}$ , as generated recursively by means of 3.61, 3.62, are also periodic, with

c^{[r]} (j + d^{r} (M + 1)) = c^{[r]} (j), j \in Z, r = 1, 2 \dots,

5.89

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

Φ_{c, m} (x + M + 1) = Φ_{c, m} (x), x \in R,

5.90

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

Proof â–¼

By applying the subdivision formulation 3.61, 3.62, we deduce

that, for any fixed $j \in Z$ ,

\begin{aligned} c^{[r + 1]} (j + d^{r + 1} (M + 1)) & = \sum_{k} p_{m, d} (j - d {k - d^{r} (M + 1)}) c^{[r]} (k) \\ = \sum_{k} p_{m, d} (j - d k) c^{[r]} (k + d^{r} (M + 1)), r = 0, 1, \dots . \end{aligned}

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 R$ ,

\begin{aligned} Φ_{c, m} (x + M + 1) & = \sum_{k} c (k) ϕ_{m} (x - {k - (M + 1)}) \\ = \sum_{k} c (k + M + 1) ϕ_{m} (x - k) = \sum_{k} c (k) ϕ_{m} (x - k) = Φ_{c, m} (x), \end{aligned}

which completes our proof of 5.90.

Proof â–¼

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

With the view to graphical implementation, for any integers $d \geq 2$ , $m \geq 3$ and
$M \geq max {2, ⌊ {(d - 1) (⌊ \frac{m}{2} ⌋ + 1)} / d ⌋}$ , let ${c (0) \dots, c (M)}$ , denote an arbitrarily chosen ordered sequence of control points in $R^{s}$ , for $s = 2$ or $s = 3$ , and with $c (0) \neq 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, \dots$ , the subdivision sequence

\begin{array}{r} {c_{m, d}^{[r]} (j) : j = 0, \dots, d^{r} (M + 1) - 1}, \end{array}

as recursively computed by means of

c_{m, d}^{[0]} (j) := c (j), j = 0, \dots, M;

and

\begin{array}{r} c_{m, d}^{[r + 1]} (d j + ℓ) := \sum_{k = - ⌊ {(d - 1) ⌊ \frac{m}{2} ⌋ + ℓ} / d ⌋}^{⌊ {(d - 1) ⌊ \frac{m + 1}{2} ⌋ - ℓ} / d ⌋} w_{m, d}^{[ℓ]} (k) c^{[r]} (j - k); ℓ = 0, \dots, d - 1, \\ j = 0, \dots, d^{r} (M + 1) - 1, \end{array}

where

\begin{array}{r} c_{m, d}^{[r]} (j) := c^{[r]} (j + d^{r} (M + 1)), j = - ⌊ {(d - 1) ⌊ \frac{m + 1}{2} ⌋} / d ⌋, \dots, - 1; \\ c_{m, d}^{[r]} (d^{r} (M + 1) - 1 + j) := c^{[r]} (j - 1), j = 1, \dots, ⌊ {(d - 1) (⌊ \frac{m}{2} ⌋ + 1)} / d ⌋ . \end{array}

For sufficiently large $r \in N$ , the points 5.92 then render the graph of the closed parametric cardinal spline curve $Φ_{c, m} : R \to 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$ .