Subdivision depth for triangular surfaces

Abstract

The aim of this attempt was to present an efficient algorithm for the evaluation of error bound of triangular subdivision surfaces. The error estimation technique is based on first order difference and this process is independent of parametrization. This technique can be easily generalized to higher arity triangular surfaces. The estimated error bound is expressed in-terms of initial control point sequence and constants. Here, we efficiently estimate error bound between triangular surface and its control polygon after k-fold subdivision and further extended to evaluate subdivision depth of the scheme.

Keywords

Subdivision surfaces; Control polygon; B-spline; Triangular surface; Error bound; Subdivision depth

1. Introduction

Subdivision is a simple and popular method to generate smooth limit curves and surfaces from discrete set of data points. It is an iterative algorithm, which is based on simple refinement rules to generate increasingly dense sequence of points under suitable hypothesis, converging to a continuous and smooth function. Starting from an initial control polygon, a subdivision scheme refers the computed values at the previous step according to the subdivision rules. The scheme is said to be convergent if there exists a limit curve. Efficiency of subdivision schemes is their flexibility and simplicity and they found their way into wide range of applications in computer graphics, medical imaging, industrial design and automotive design, etc. [1], [2] and [3].

Triangular surfaces [4] are one of the fundamental paradigms of Computer Aided Geometric Design (CAGD). These are defined by de Boor nets and have a regular triangular structure. This class of triangular surfaces shares the properties of univariate [5] and tensor product B-splines [6]. The procedure for subdividing triangular surfaces exactly parallels the subdivision for tensor product B-spline surfaces. Actually, these are extension of B-splines surfaces.

For many applications such as rendering, intersection testing or design, it is important to know, how well the control polygon approximate the exact curve or a surface. In the last decade several researchers attempt to answer the question and to improve the rule to estimate error bounds. The techniques presented in [7], [8], [9], [10] and [11] for computation of error bounds are based on parametrization, so they cannot be generalized to subdivision surfaces easily, methods presented in [12], [13] and [14] are based on eigen analysis. Zeng and Chen [15] introduced the concept of neighbor points and by using the first-order difference of control points of Catmull–Clark surfaces, they obtained the rate of convergence of control meshes of Catmull–Clark surface. From the result of convergence, they derived a computational formula of subdivision depth for Catmull–Clark surfaces. Cheng and Yong [16] introduced computational formula for subdivision depth, which is based on second order forward differences for extra-ordinary Catmull–Clark subdivision surface patches. Mustafa et al. [17], [18], [19], [20], [21], [22] and [23] have estimated error bound for binary, ternary, quaternary, non-stationary, n-ary curve, surface and volumetric model in-terms of maximal first order differences of the initial control point sequence and constants that depend on the subdivision mask. Huang et al. [24] derive a bound on the distance between a Catmull Clark subdivision surface patch and its limit face in terms of the maximum norm of the second order differences of the control points and a constant that depends only on the valence of the patch. Later on Mustafa et al. estimate the subdivision depth of Bajaj and ${\textstyle {\sqrt {3}}}$ subdivision schemes for both regular and irregular patches [25] and [26]. Moncayo and Amat [27] presented error bounds for a class of subdivision schemes based on the two-scale refinement equation. In recent years Hashmi et al. [28] estimated the subdivision depth for Li subdivision scheme for regular and irregular patches.

In the present literature survey, it is evident that no such attempt has been made to evaluate subdivision depth for triangular subdivision surfaces. In this paper author successfully articulates the formula for subdivision depth for triangular surfaces based on first order differences by using estimation techniques.

The rest of the paper is arranged in following fashion: Some definition and preliminary notations are given in Section 2. Section 3 is devoted for the proof of main result based on some preliminary results. Future research directions are given in Section 4. To maintain the presentation of paper as simple as possible for readers, notations and typical mathematical proof of basic results are provided in the Appendices.

2. Definition and notations

Let ${\textstyle p_{i{\mbox{,}}j}^{k}\in R^{N}}$, ${\textstyle i{\mbox{,}}j\in Z}$, denote a sequence of points in ${\textstyle R^{N}}$, ${\textstyle N\geqslant 2}$, where k is a non-negative integer then binary subdivision process for triangular surfaces [1, pp. 14–19] in our context can be restated as

$p_{i+(m+\alpha -1)/2{\mbox{,}}j+(m+\beta -1)/2}^{k+1}=$$\sum _{r=-m+1}^{m-1}\sum _{s=-m+1}^{m-1}\sum _{l=0}^{m}a_{\alpha {\mbox{,}}r{\mbox{,}}l}a_{\beta {\mbox{,}}s{\mbox{,}}l}d_{m{\mbox{,}}l}p_{i+r{\mbox{,}}j+s}^{k}{\mbox{,}}$

(2.1)

where ${\textstyle \alpha {\mbox{,}}\beta \in \lbrace 0{\mbox{,}}1\rbrace }$ or ${\textstyle \lbrace 1{\mbox{,}}2\rbrace {\mbox{,}}m}$ is greater than 2, ${\textstyle a_{\alpha {\mbox{,}}j{\mbox{,}}l}}$ and ${\textstyle d_{m{\mbox{,}}l}}$ are defined by

$a_{\alpha {\mbox{,}}j{\mbox{,}}l}=2^{-m}\left({\begin{array}{c}m\\2({\frac {m+\alpha -1}{2}}-j)-l\end{array}}\right){\mbox{,}}\quad d_{m{\mbox{,}}l}=2^{-m+2}\left({\begin{array}{c}m\\l\end{array}}\right){\mbox{,}}$

for ${\textstyle \alpha =0{\mbox{,}}1{\mbox{,}}2}$, ${\textstyle j=-m+1{\mbox{,}}\ldots {\mbox{,}}m-1}$, ${\textstyle l=0{\mbox{,}}\ldots {\mbox{,}}m}$, called subdivision mask. It is cautioned that (2.1) depends on labeling of the control polygon. For example for m = 2, 3, and 4, labeling of old and new points (${\textstyle A{\mbox{,}}B{\mbox{,}}C{\mbox{,}}D{\mbox{,}}E{\mbox{,}}F{\mbox{,}}G}$) is shown in Figs. 1(a) and (b) and 2 respectively.

Figure 1. (a) ${\textstyle A=p_{i+{\frac {1}{2}}{\mbox{,}}j+{\frac {1}{2}}}}$, ${\textstyle B=p_{i+{\frac {1}{2}}{\mbox{,}}j+1}}$, ${\textstyle C=p_{i+1{\mbox{,}}j+{\frac {1}{2}}}}$, ${\textstyle D=p_{i+1{\mbox{,}}j+1}}$, ${\textstyle E=p_{i+1{\mbox{,}}j+{\frac {3}{2}}}}$, ${\textstyle F=p_{i+{\frac {3}{2}}{\mbox{,}}j+1}}$, ${\textstyle G=p_{i+{\frac {3}{2}}{\mbox{,}}j+{\frac {3}{2}}}}$. (b) ${\textstyle A=p_{i+1{\mbox{,}}j+1}}$, ${\textstyle B=p_{i+1{\mbox{,}}j+{\frac {3}{2}}}}$, ${\textstyle C=p_{i+{\frac {3}{2}}{\mbox{,}}j+1}}$, ${\textstyle D=p_{i+{\frac {3}{2}}{\mbox{,}}j+{\frac {3}{2}}}}$, ${\textstyle E=p_{i+{\frac {3}{2}}{\mbox{,}}j+2}}$, ${\textstyle F=p_{i+2{\mbox{,}}j+{\frac {3}{2}}}}$, ${\textstyle G=p_{i+2{\mbox{,}}j+2}}$.

Figure 2. Here m = 4, ${\textstyle A=p_{i+{\frac {3}{2}}{\mbox{,}}j+{\frac {3}{2}}}}$, ${\textstyle B=p_{i+{\frac {3}{2}}{\mbox{,}}j+2}}$, ${\textstyle C=p_{i+2{\mbox{,}}j+{\frac {3}{2}}}}$, ${\textstyle D=p_{i+2{\mbox{,}}j+2}}$, ${\textstyle E=p_{i+2{\mbox{,}}j+{\frac {5}{2}}}}$, ${\textstyle F=p_{i+{\frac {5}{2}}{\mbox{,}}j+2}}$, ${\textstyle G=p_{i+{\frac {5}{2}}{\mbox{,}}j+{\frac {5}{2}}}}$.

Given initial values ${\textstyle p_{i{\mbox{,}}j}^{0}\in R^{N}}$, ${\textstyle i{\mbox{,}}j\in Z}$, then in the limit ${\textstyle k\rightarrow \infty }$, the process defines an infinite set of points in ${\textstyle R^{N}}$. A necessary condition for the convergence of the subdivision process (2.1) for arbitrary initial data is that

$\sum _{r=-m+1}^{m-1}\sum _{s=-m+1}^{m-1}\sum _{l=0}^{m}a_{\alpha {\mbox{,}}r{\mbox{,}}l}a_{\beta {\mbox{,}}s{\mbox{,}}l}d_{m{\mbox{,}}l}=$$1{\mbox{,}}$

(2.2)

where ${\textstyle \alpha {\mbox{,}}\beta \in \lbrace 0{\mbox{,}}1\rbrace }$ or ${\textstyle \left\{1{\mbox{,}}2\right\}}$.

Let us suppose

${\beta }_{t}^{k}={\underset {i{\mbox{,}}j}{max}}\left\|{\Delta }_{i{\mbox{,}}j{\mbox{,}}t}^{k}\right\|{\mbox{,}}\quad k\geqslant 0{\mbox{,}}\quad t=$$1{\mbox{,}}2{\mbox{,}}$

(2.3)

where

${\begin{array}{ll}{\Delta }_{i{\mbox{,}}j{\mbox{,}}1}^{k}=p_{i+r+1{\mbox{,}}j+s}^{k}-p_{i+r{\mbox{,}}j+s}^{k}{\mbox{,}}&\forall \quad r{\mbox{,}}s\in Z{\mbox{,}}\\{\Delta }_{i{\mbox{,}}j{\mbox{,}}2}^{k}=p_{i+s{\mbox{,}}j+r+1}^{k}-p_{i+s{\mbox{,}}j+r}^{k}{\mbox{,}}&\forall \quad r{\mbox{,}}s\in Z{\mbox{.}}\end{array}}$

(2.4)

Suppose for ${\textstyle \alpha =0{\mbox{,}}1{\mbox{,}}2}$,

${\begin{array}{l}{\xi }_{\alpha {\mbox{,}}l}^{1}=\sum _{p=1}^{m-1}a_{\alpha {\mbox{,}}p{\mbox{,}}l}{\mbox{,}}\quad {\xi }_{\alpha {\mbox{,}}l}^{2}=\sum _{p=-1}^{-m+1}a_{\alpha {\mbox{,}}p{\mbox{,}}l}{\mbox{,}}\quad {\xi }_{\alpha {\mbox{,}}l}^{3}=\sum _{r=-m+1}^{m-1}a_{\alpha {\mbox{,}}r{\mbox{,}}l}{\mbox{,}}\\{\xi }_{\alpha {\mbox{,}}l}^{4}=\sum _{q=1}^{m-2}{\tilde {a}}_{\alpha {\mbox{,}}q{\mbox{,}}l}-\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{\alpha {\mbox{,}}q+1{\mbox{,}}l}{\mbox{,}}\end{array}}$

(2.5)

where

${\tilde {a}}_{\alpha {\mbox{,}}q{\mbox{,}}l}=\sum _{j=q+1}^{m}a_{\alpha {\mbox{,}}j{\mbox{,}}l}{\mbox{,}}\quad {\tilde {\tilde {a}}}_{\alpha {\mbox{,}}q+1{\mbox{,}}l}=$$\sum _{j=q}^{-m+1}a_{\alpha {\mbox{,}}j{\mbox{,}}l}{\mbox{.}}$

Suppose further that

$M_{\left(\alpha {\mbox{,}}\beta \right)}^{k}={\underset {i{\mbox{,}}j}{max}}\left\|p_{i+(m+\alpha -1)/2{\mbox{,}}j+(m+\beta -1)/2}^{k+1}-\right.$$\left.{\frac {1}{2}}\left(p_{i{\mbox{,}}j}^{k}+p_{i+\alpha -1{\mbox{,}}j+\beta -1}^{k}\right)\right\|{\mbox{,}}$

(2.6)

where ${\textstyle \alpha {\mbox{,}}\beta \in \lbrace 0{\mbox{,}}1\rbrace }$ or ${\textstyle \left\{1{\mbox{,}}2\right\}}$.

Also

$\delta =max\left\{{\begin{array}{l}\left|\sum _{l=0}^{m}\sum _{s=-m+1}^{m-1}\sum _{r=-m+1}^{m-2}a_{1{\mbox{,}}s{\mbox{,}}l}d_{m{\mbox{,}}l}e_{r{\mbox{,}}l}\right|{\mbox{,}}\left|\sum _{l=0}^{m}\sum _{s=-m+1}^{m-1}\sum _{r=-m+1}^{m-2}a_{1{\mbox{,}}s{\mbox{,}}l}d_{m{\mbox{,}}l}f_{r{\mbox{,}}l}\right|{\mbox{,}}\\\left|\sum _{l=0}^{m}\sum _{s=-m+1}^{m-1}\sum _{r=-m+1}^{m-2}a_{2{\mbox{,}}s{\mbox{,}}l}d_{m{\mbox{,}}l}e_{r{\mbox{,}}l}\right|{\mbox{,}}\left|\sum _{l=0}^{m}\sum _{s=-m+1}^{m-1}\sum _{r=-m+1}^{m-2}a_{0{\mbox{,}}s{\mbox{,}}l}d_{m{\mbox{,}}l}f_{r{\mbox{,}}l}\right|{\mbox{,}}\end{array}}\right\}$

(2.7)

where ${\textstyle e_{r{\mbox{,}}l}={\sum }_{p=-m+1}^{r}(a_{1{\mbox{,}}p{\mbox{,}}l}-}$$a_{2{\mbox{,}}p{\mbox{,}}l})$ and ${\textstyle f_{r{\mbox{,}}l}={\sum }_{p=-m+1}^{r}(a_{0{\mbox{,}}p{\mbox{,}}l}-}$$a_{1{\mbox{,}}p{\mbox{,}}l})$.

Rest of the notations are in Appendix A.

2.1. Subdivision depth

Given control polygon of n  -ary subdivision surface and an error tolerance ${\textstyle \in }$, if we subdivide control polygon k   times, so that the error between resulting polygon and subdivision surface is smaller than ${\textstyle \in }$, then k   is called subdivision depth of subdivision surface with respect to ${\textstyle \in }$.

3. The error bounds for triangular surfaces

In this Section, the main result for error bounds is presented for triangular surfaces, which is based on some preliminary results. Finally, the section ends on subdivision depth formula.

Lemma 3.1.

Given initial triangular control polygon  ${\textstyle p_{i{\mbox{,}}j}^{0}=p_{i{\mbox{,}}j}}$,  ${\textstyle i{\mbox{,}}j\in Z}$, let the values  ${\textstyle p_{i{\mbox{,}}j}^{k}{\mbox{,}}k\geqslant 0}$be defined recursively by subdivision process(2.1)together with(2.2)then

${\beta }_{t}^{k}\leqslant {\left(\delta \right)}^{k}{\beta }_{t}^{0}{\mbox{,}}\quad t=$$1{\mbox{,}}2{\mbox{,}}$

(3.1)

where  ${\textstyle {\beta }_{t}^{k}}$for  ${\textstyle k\geqslant 0}$and  ${\textstyle \delta }$are defined by(2.3) and (2.7)respectively.

Proof.

Proof is shown in . □

The proof of following Lemma is shown in .

Lemma 3.2.

Given initial triangular control polygon  ${\textstyle p_{i{\mbox{,}}j}^{0}=p_{i{\mbox{,}}j}}$,  ${\textstyle i{\mbox{,}}j\in Z}$, let the values  ${\textstyle p_{i{\mbox{,}}j}^{k}{\mbox{,}}\quad k\geqslant 0}$be defined recursively by subdivision process(2.1)together with(2.2)then

$M_{\left(1{\mbox{,}}1\right)}^{k}\leqslant {\left(\delta \right)}^{k}\sum _{t=1}^{2}{\eta }_{1}^{t}{\beta }_{t}^{0}{\mbox{,}}$

(3.2)

where  ${\textstyle {\beta }_{t}^{0}{\mbox{,}}M_{\left(1{\mbox{,}}1\right)}^{k}{\mbox{,}}\delta }$and  ${\textstyle {\eta }_{1}^{t}}$are defined by(2.3), (2.6), (2.7) and (A.1)respectively.

Lemma 3.3.

Given initial triangular control polygon  ${\textstyle p_{i{\mbox{,}}j}^{0}=p_{i{\mbox{,}}j}}$,  ${\textstyle i{\mbox{,}}j\in Z}$, let the values  ${\textstyle p_{i{\mbox{,}}j}^{k}{\mbox{,}}k\geqslant 0}$be defined recursively by subdivision process(2.1)together with(2.2)then

$M_{\left(2{\mbox{,}}1\right)}^{k}\leqslant {\left(\delta \right)}^{k}\sum _{t=1}^{2}{\eta }_{2}^{t}{\beta }_{t}^{0}{\mbox{,}}$

(3.3)

where  ${\textstyle {\beta }_{t}^{0}{\mbox{,}}M_{\left(2{\mbox{,}}1\right)}^{k}{\mbox{,}}\delta }$and  ${\textstyle {\eta }_{2}^{t}}$are defined by(2.3), (2.6), (2.7) and (A.2)respectively.

Proof.

Proof is given in . □

Similarly, one can prove the following lemma.

Lemma 3.4.

Given initial triangular control polygon  ${\textstyle p_{i{\mbox{,}}j}^{0}=p_{i{\mbox{,}}j}}$,  ${\textstyle i{\mbox{,}}j\in Z}$, let the values  ${\textstyle p_{i{\mbox{,}}j}^{k}{\mbox{,}}\quad k\geqslant 0}$be defined recursively by subdivision process(2.1)together with(2.2)then

$M_{\chi }^{k}\leqslant {\left(\delta \right)}^{k}\sum _{t=1}^{2}{\eta }_{\upsilon }^{t}{\beta }_{t}^{0}{\mbox{,}}\quad \upsilon =$$3{\mbox{,}}4{\mbox{,}}5{\mbox{,}}6{\mbox{,}}7{\mbox{,}}$

(3.4)

where  ${\textstyle {\beta }_{t}^{0}}$,  ${\textstyle M_{\chi }^{k}}$,  ${\textstyle \chi \in \left\{\left(1{\mbox{,}}2){\mbox{,}}(2{\mbox{,}}2){\mbox{,}}(0{\mbox{,}}1){\mbox{,}}(1{\mbox{,}}0){\mbox{,}}(0{\mbox{,}}0\right)\right\}}$,  ${\textstyle \delta }$and  ${\textstyle {\eta }_{\upsilon }^{t}}$are defined by(2.3), (2.6) and (2.7) and (A.3), (A.4), (A.5), (A.6) and (A.7)respectively. There is following correspondence between the values of v and  ${\textstyle \chi }$:  ${\textstyle 3\rightarrow (1{\mbox{,}}2)}$,  ${\textstyle 4\rightarrow (2{\mbox{,}}2)}$,  ${\textstyle 5\rightarrow (0{\mbox{,}}1)}$,  ${\textstyle 6\rightarrow (1{\mbox{,}}0)}$and  ${\textstyle 7\rightarrow (0{\mbox{,}}0)}$.

Here, we present our main result to estimate error bounds between triangular surface and its control polygon after k-fold subdivision.

Theorem 3.5.

Given initial triangular control polygon  ${\textstyle p_{i{\mbox{,}}j}^{0}=p_{i{\mbox{,}}j}}$,  ${\textstyle i{\mbox{,}}j\in Z}$, let the values  ${\textstyle p_{i{\mbox{,}}j}^{k}{\mbox{,}}k\geqslant 0}$be defined recursively by subdivision process(2.1)together with(2.2). Suppose  ${\textstyle P^{k}}$be the piecewise linear interpolation to the values  ${\textstyle p_{i{\mbox{,}}j}^{k}}$and  ${\textstyle P^{\infty }}$be the limit triangular surface of the subdivision process(2.1). If  ${\textstyle \delta <1}$then error bounds between triangular surface and its control polygon after k-fold subdivision are

${\left\|P^{k}-P^{\infty }\right\|}_{\infty }\leqslant \gamma \left({\frac {{\left(\delta \right)}^{k}}{1-\delta }}\right){\mbox{,}}$

(3.5)

where  ${\textstyle \delta }$and  ${\textstyle \gamma }$are defined by(2.7) and (A.8)respectively.

Proof.

Let ${\textstyle {\left\|\cdot \right\|}_{\infty }}$ denote the uniform norm. Since the maximum difference between ${\textstyle P^{k+1}}$ and ${\textstyle P^{k}}$ is attained at a point on the ${\textstyle \left(k+1\right)}$th control polygon (i.e. control polygon after ${\textstyle \left(k+1\right)}$-fold subdivision), then

${\left\|P^{k+1}-P^{k}\right\|}_{\infty }\leqslant max\left\{M_{\left(\alpha {\mbox{,}}\beta \right)}^{k}\right\}{\mbox{,}}$

(3.6)

where ${\textstyle M_{\left(\alpha {\mbox{,}}\beta \right)}^{k}}$ is defined by (2.6).

Then from (3.2), (3.3), (3.4) and (3.6) we get

${\left\|P^{k+1}-P^{k}\right\|}_{\infty }\leqslant \gamma {\left(\delta \right)}^{k}{\mbox{,}}$

where ${\textstyle \delta }$ and ${\textstyle \gamma }$ are defined by (2.7) and (A.8) respectively.

Using triangular inequality we get

${\left\|P^{k}-P^{\infty }\right\|}_{\infty }\leqslant \gamma \left({\frac {{\left(\delta \right)}^{k}}{1-\delta }}\right){\mbox{,}}$

This completes the proof. □

Remark 3.1.

It is pointed out that, most of the famous binary triangular subdivision schemes satisfies the condition ${\textstyle \delta <1}$. Our claim is supported by the following corollaries.

Corollary 3.6.

Given initial triangular control polygon  ${\textstyle p_{i{\mbox{,}}j}^{0}=p_{i{\mbox{,}}j}}$,  ${\textstyle i{\mbox{,}}j\in Z}$, let the values  ${\textstyle p_{i{\mbox{,}}j}^{k}{\mbox{,}}k\geqslant 0}$be defined recursively by subdivision process(2.1)for  ${\textstyle m=2{\mbox{,}}3{\mbox{,}}4}$. Suppose  ${\textstyle P^{k}}$be the piecewise linear interpolation to the values  ${\textstyle p_{i{\mbox{,}}j}^{k}}$and  ${\textstyle P^{\infty }}$be the limit triangular surface of the subdivision process. Then

${\left\|P^{k}-P^{\infty }\right\|}_{\infty }\leqslant \left\{{\begin{array}{ll}{\frac {1}{4}}{\beta }_{1}^{0}+{\frac {1}{4}}{\beta }_{2}^{0}{\mbox{,}}&m=2\\{\frac {3}{8}}{\beta }_{1}^{0}+{\frac {3}{8}}{\beta }_{2}^{0}{\mbox{,}}&m=3\\{\frac {239}{512}}{\beta }_{1}^{0}+{\frac {29}{64}}{\beta }_{2}^{0}{\mbox{,}}&m=4\end{array}}\right\}{\left({\frac {1}{2}}\right)}^{k-1}$

where  ${\textstyle {\beta }_{t}^{0}{\mbox{,}}t=1{\mbox{,}}2}$are defined by(2.3).

Theorem 3.7.

Let k be subdivision depth and let  ${\textstyle d^{k}}$be the error bound between triangular subdivision surface  ${\textstyle P^{\infty }}$and its k-level control polygon  ${\textstyle P^{k}}$. For arbitrary  ${\textstyle \in >0}$, if

$k\geqslant {log}_{{\delta }^{-1}}\left({\frac {\gamma }{\in (1-\delta )}}\right){\mbox{,}}$

(3.7)

then

$d^{k}\leqslant \in {\mbox{.}}$

Proof.

From (3.5), we have

$d^{k}={\left\|P^{k}-P^{\infty }\right\|}_{\infty }\leqslant \gamma \left({\frac {{\left(\delta \right)}^{k}}{1-\delta }}\right){\mbox{.}}$

This implies, for arbitrary given ${\textstyle \in >0}$, when subdivision depth k satisfies the following inequality

$k\geqslant {log}_{{\delta }^{-1}}\left({\frac {\gamma }{\in (1-\delta )}}\right){\mbox{,}}$

then

$d^{k}\leqslant \in {\mbox{.}}$

This completes the proof. □

4. Future work

The technique presented in this article can be generalized to estimate error bounds between ternary and obviously to n-ary triangular surface and its control polygon after k-fold subdivision. The attempt can also be made to estimate subdivision depth for irregular triangular patches.

Appendix A. Notations

We have the following

${\begin{array}{l}{\eta }_{1}^{1}=\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{1{\mbox{,}}l}^{2}\right|+\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{1{\mbox{,}}l}^{1}\right|+{\left|{\xi }_{1{\mbox{,}}l}^{2}\right|}^{2}+2\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{1{\mbox{,}}l}^{1}\right|+{\left|{\xi }_{1{\mbox{,}}l}^{1}\right|}^{2}\\\quad +\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{1{\mbox{,}}l}^{4}\right|+\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{1{\mbox{,}}l}^{4}\right|+\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{1{\mbox{,}}l}^{4}\right|{\mbox{,}}\\{\eta }_{1}^{2}=\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left\{\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{1{\mbox{,}}l}^{3}\right|+\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{1{\mbox{,}}l}^{3}\right|+\left|{\xi }_{1{\mbox{,}}l}^{3}{\xi }_{1{\mbox{,}}l}^{4}\right|\right\}{\mbox{.}}\end{array}}$

(A.1)

${\begin{array}{l}{\eta }_{2}^{1}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}2\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{2}\right|+\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{1}-\left(a_{2{\mbox{,}}0{\mbox{,}}l}+{\xi }_{2{\mbox{,}}l}^{2}\right){\xi }_{1{\mbox{,}}l}^{3}\right|+2\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{2}\right|\\\quad +\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{1}\right|+2\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{2}\right|+\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{1}\right|+2\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{4}\right|+2\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{4}\right|+2\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{4}\right|{\mbox{,}}\\{\eta }_{2}^{2}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left|\left(a_{2{\mbox{,}}0{\mbox{,}}l}+{\xi }_{2{\mbox{,}}l}^{2}+{\xi }_{2{\mbox{,}}l}^{3}\right){\xi }_{1{\mbox{,}}l}^{2}\right|+\left|\left(a_{2{\mbox{,}}0{\mbox{,}}l}+{\xi }_{2{\mbox{,}}l}^{2}+{\xi }_{2{\mbox{,}}l}^{3}\right){\xi }_{1{\mbox{,}}l}^{1}\right|\\\quad +\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{1}\right|+\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{1}\right|+2\left|{\xi }_{2{\mbox{,}}l}^{3}{\xi }_{1{\mbox{,}}l}^{4}\right|{\mbox{.}}\end{array}}$

(A.2)

${\begin{array}{l}{\eta }_{3}^{1}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left|\left(2a_{2{\mbox{,}}0{\mbox{,}}l}+{\xi }_{2{\mbox{,}}l}^{2}\right){\xi }_{1{\mbox{,}}l}^{2}\right|+\left|\left(2a_{2{\mbox{,}}0{\mbox{,}}l}+{\xi }_{2{\mbox{,}}l}^{2}\right){\xi }_{1{\mbox{,}}l}^{1}\right|+\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{2}\right|\\\quad +2\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{1}\right|+\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{2}\right|+2\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{1}\right|+2\left|a_{2{\mbox{,}}0{\mbox{,}}l}{\xi }_{1{\mbox{,}}l}^{4}\right|+2\left|{\xi }_{2{\mbox{,}}l}^{2}{\xi }_{1{\mbox{,}}l}^{4}\right|+2\left|{\xi }_{2{\mbox{,}}l}^{1}{\xi }_{1{\mbox{,}}l}^{4}\right|{\mbox{,}}\\{\eta }_{3}^{2}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left\{\left|{\xi }_{1{\mbox{,}}l}^{3}\left({\xi }_{2{\mbox{,}}l}^{2}+{\xi }_{2{\mbox{,}}l}^{1}-a_{2{\mbox{,}}0{\mbox{,}}l}\right)\right|+2\left|{\xi }_{1{\mbox{,}}l}^{3}{\xi }_{2{\mbox{,}}l}^{2}\right|+2\left|{\xi }_{1{\mbox{,}}l}^{3}{\xi }_{2{\mbox{,}}l}^{4}\right|\right\}{\mbox{.}}\end{array}}$

(A.3)

${\begin{array}{l}{\eta }_{4}^{1}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left|\left(2a_{2{\mbox{,}}0{\mbox{,}}l}+{\xi }_{2{\mbox{,}}l}^{2}\right){\xi }_{2{\mbox{,}}l}^{2}\right|+\left|a_{2{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{1}\right|+{\left|{\xi }_{2{\mbox{,}}l}^{2}\right|}^{2}+3\left|{\xi }_{2{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{1}\right|\\\quad +\left|{\left({\xi }_{2{\mbox{,}}l}^{1}\right)}^{2}-\left(a_{2{\mbox{,}}0{\mbox{,}}l}+{\xi }_{2{\mbox{,}}l}^{2}\right){\xi }_{2{\mbox{,}}l}^{2}\right|+2\left|a_{2{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{4}\right|+2\left|{\xi }_{2{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{4}\right|+2\left|{\xi }_{2{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{4}\right|{\mbox{,}}\\{\eta }_{4}^{2}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}2\left|{\xi }_{2{\mbox{,}}l}^{3}{\xi }_{2{\mbox{,}}l}^{2}\right|+\left|{\xi }_{2{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{3}-{\left(a_{2{\mbox{,}}0{\mbox{,}}l}+{\xi }_{2{\mbox{,}}l}^{2}\right)}^{2}\right|+\left|{\xi }_{2{\mbox{,}}l}^{1}(a_{2{\mbox{,}}0{\mbox{,}}l}+{\xi }_{2{\mbox{,}}l}^{2})\right|\\\quad +2\left|{\xi }_{2{\mbox{,}}l}^{3}{\xi }_{2{\mbox{,}}l}^{4}\right|{\mbox{.}}\end{array}}$

(A.4)

${\begin{array}{l}{\eta }_{5}^{1}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{0{\mbox{,}}l}^{2}-\left(a_{0{\mbox{,}}0{\mbox{,}}l}+{\xi }_{0{\mbox{,}}l}^{1}\right){\xi }_{1{\mbox{,}}l}^{3}\right|+2\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{0{\mbox{,}}l}^{1}\right|+2\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{0{\mbox{,}}l}^{1}\right|\\\quad +2\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{0{\mbox{,}}l}^{1}\right|+\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{0{\mbox{,}}l}^{2}\right|+\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{0{\mbox{,}}l}^{2}\right|+2\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{0{\mbox{,}}l}^{4}\right|+2\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{0{\mbox{,}}l}^{4}\right|+2\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{0{\mbox{,}}l}^{4}\right|{\mbox{,}}\\{\eta }_{5}^{2}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left|{\xi }_{1{\mbox{,}}l}^{2}\left(a_{0{\mbox{,}}0{\mbox{,}}l}+{\xi }_{0{\mbox{,}}l}^{2}+{\xi }_{0{\mbox{,}}l}^{3}\right)\right|+\left|{\xi }_{1{\mbox{,}}l}^{1}\left(a_{0{\mbox{,}}0{\mbox{,}}l}+{\xi }_{0{\mbox{,}}l}^{2}+{\xi }_{0{\mbox{,}}l}^{3}\right)\right|\\\quad +\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{0{\mbox{,}}l}^{2}\right|+\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{0{\mbox{,}}l}^{2}\right|+2\left|{\xi }_{0{\mbox{,}}l}^{3}{\xi }_{1{\mbox{,}}l}^{4}\right|{\mbox{.}}\end{array}}$

(A.5)

${\begin{array}{l}{\eta }_{6}^{1}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left|\left(2a_{0{\mbox{,}}0{\mbox{,}}l}+{\xi }_{0{\mbox{,}}l}^{1}\right){\xi }_{1{\mbox{,}}l}^{2}\right|+\left|\left(2a_{0{\mbox{,}}0{\mbox{,}}l}+{\xi }_{0{\mbox{,}}l}^{1}\right){\xi }_{1{\mbox{,}}l}^{1}\right|+2\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{0{\mbox{,}}l}^{2}\right|\\\quad +2\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{0{\mbox{,}}l}^{2}\right|+\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{0{\mbox{,}}l}^{1}\right|+\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{0{\mbox{,}}l}^{1}\right|+2\left|a_{0{\mbox{,}}0{\mbox{,}}l}{\xi }_{1{\mbox{,}}l}^{4}\right|+2\left|{\xi }_{0{\mbox{,}}l}^{2}{\xi }_{1{\mbox{,}}l}^{4}\right|+2\left|{\xi }_{0{\mbox{,}}l}^{1}{\xi }_{1{\mbox{,}}l}^{4}\right|{\mbox{,}}\\{\eta }_{6}^{2}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left\{\left|{\xi }_{1{\mbox{,}}l}^{3}\left(a_{0{\mbox{,}}0{\mbox{,}}l}+{\xi }_{0{\mbox{,}}l}^{1}-{\xi }_{0{\mbox{,}}l}^{2}\right)\right|+2\left|{\xi }_{0{\mbox{,}}l}^{1}{\xi }_{1{\mbox{,}}l}^{3}\right|+2\left|{\xi }_{1{\mbox{,}}l}^{3}{\xi }_{0{\mbox{,}}l}^{4}\right|\right\}{\mbox{.}}\end{array}}$

(A.6)

${\begin{array}{l}{\eta }_{7}^{1}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left|a_{0{\mbox{,}}0{\mbox{,}}l}{\xi }_{0{\mbox{,}}l}^{2}\right|+\left|\left(2a_{0{\mbox{,}}0{\mbox{,}}l}+{\xi }_{0{\mbox{,}}l}^{1}\right){\xi }_{0{\mbox{,}}l}^{1}\right|+3\left|{\xi }_{0{\mbox{,}}l}^{1}{\xi }_{0{\mbox{,}}l}^{2}\right|+{\left|{\xi }_{0{\mbox{,}}l}^{1}\right|}^{2}+\left|{\xi }_{0{\mbox{,}}l}^{1}{\xi }_{0{\mbox{,}}l}^{4}\right|\\\quad +\left|{\left({\xi }_{0{\mbox{,}}l}^{2}\right)}^{2}-\left(a_{0{\mbox{,}}0{\mbox{,}}l}+{\xi }_{0{\mbox{,}}l}^{1}\right){\xi }_{0{\mbox{,}}l}^{3}\right|+2\left|a_{0{\mbox{,}}0{\mbox{,}}l}{\xi }_{0{\mbox{,}}l}^{4}\right|+2\left|{\xi }_{0{\mbox{,}}l}^{2}{\xi }_{0{\mbox{,}}l}^{4}\right|+\left|{\xi }_{0{\mbox{,}}l}^{1}{\xi }_{0{\mbox{,}}l}^{4}\right|{\mbox{,}}\\{\eta }_{7}^{2}={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left|{\xi }_{0{\mbox{,}}l}^{2}{\xi }_{0{\mbox{,}}l}^{3}-{\left(a_{0{\mbox{,}}0{\mbox{,}}l}+{\xi }_{0{\mbox{,}}l}^{1}\right)}^{2}\right|+2\left|{\xi }_{0{\mbox{,}}l}^{1}{\xi }_{0{\mbox{,}}l}^{3}\right|+2\left|{\xi }_{0{\mbox{,}}l}^{3}{\xi }_{0{\mbox{,}}l}^{4}\right|\\\quad +\left|\left(a_{0{\mbox{,}}0{\mbox{,}}l}+{\xi }_{0{\mbox{,}}l}^{1}\right){\xi }_{0{\mbox{,}}l}^{2}\right|{\mbox{,}}\end{array}}$

(A.7)

and

$\gamma =max\left\{\sum _{t=1}^{2}{\eta }_{\upsilon }^{t}{\beta }_{t}^{0}{\mbox{,}}\quad \upsilon =\right.$$\left.1{\mbox{,}}2{\mbox{,}}\ldots {\mbox{,}}7\right\}{\mbox{.}}$

(A.8)

Proof.

From (2.1) and (2.2)

$p_{i+(m+1)/2{\mbox{,}}j+(m+\alpha -1)/2}^{k}-p_{i+m/2{\mbox{,}}j+(m+\alpha -1)/2}^{k}=$$\sum _{l=0}^{m}\sum _{s=-m+1}^{m-1}d_{m{\mbox{,}}l}a_{\alpha {\mbox{,}}s{\mbox{,}}l}\left(\sum _{r=-m+1}^{m-1}\left(a_{2{\mbox{,}}r{\mbox{,}}l}-\right.\right.$$\left.\left.a_{1{\mbox{,}}r{\mbox{,}}l}\right)p_{i+r{\mbox{,}}j+s}^{k-1}\right){\mbox{,}}$

where ${\textstyle \alpha =1{\mbox{,}}2}$. By using similar approach of Mustafa et al. [17] (Theorem 1, p. 599 and Theorem 7, p. 609), we obtain

$p_{i+(m+1)/2{\mbox{,}}j+(m+\alpha -1)/2}^{k}-p_{i+m/2{\mbox{,}}j+(m+\alpha -1)/2}^{k}=$$\sum _{l=0}^{m}\sum _{s=-m+1}^{m-1}d_{m{\mbox{,}}l}a_{\alpha {\mbox{,}}s{\mbox{,}}l}\left(\sum _{r=-m+1}^{m-2}e_{r{\mbox{,}}l}\left(p_{i+r+1{\mbox{,}}j+s}^{k-1}-\right.\right.$$\left.\left.p_{i+r{\mbox{,}}j+s}^{k-1}\right)\right){\mbox{,}}$

(B.1)

where ${\textstyle e_{r{\mbox{,}}l}={\sum }_{p=-m+1}^{r}(a_{1{\mbox{,}}p{\mbox{,}}l}-}$$a_{2{\mbox{,}}p{\mbox{,}}l})$.

Similarly from (2.1) and (2.2) we have the following differences, for ${\textstyle \alpha =0{\mbox{,}}1}$

$p_{i+m/2{\mbox{,}}j+(m+\alpha -1)/2}^{k}-p_{i+(m-1)/2{\mbox{,}}j+(m+\alpha -1)/2}^{k}=$$\sum _{l=0}^{m}\sum _{s=-m+1}^{m-1}d_{m{\mbox{,}}l}a_{\alpha {\mbox{,}}s{\mbox{,}}l}\left(\sum _{r=-m+1}^{m-2}f_{r{\mbox{,}}l}\left(p_{i+r+1{\mbox{,}}j+s}^{k-1}-\right.\right.$$\left.\left.p_{i+r{\mbox{,}}j+s}^{k-1}\right)\right){\mbox{,}}$

(B.2)

where ${\textstyle f_{r{\mbox{,}}l}={\sum }_{p=-m+1}^{r}(a_{0{\mbox{,}}p{\mbox{,}}l}-}$$a_{1{\mbox{,}}p{\mbox{,}}l})$.

Further for ${\textstyle \alpha =1{\mbox{,}}2}$, we get

$p_{i+(m+\alpha -1)/2{\mbox{,}}j+(m+1)/2}^{k}-p_{i+(m+\alpha -1)/2{\mbox{,}}j+m/2}^{k}=$$\sum _{l=0}^{m}\sum _{r=-m+1}^{m-1}d_{m{\mbox{,}}l}a_{\alpha {\mbox{,}}r{\mbox{,}}l}\left(\sum _{s=-m+1}^{m-2}e_{s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s+1}^{k-1}-\right.\right.$$\left.\left.p_{i+r{\mbox{,}}j+s}^{k-1}\right)\right){\mbox{,}}$

(B.3)

For ${\textstyle \alpha =0{\mbox{,}}1}$

$p_{i+(m+\alpha -1)/2{\mbox{,}}j+m/2}^{k}-p_{i+(m+\alpha -1)/2{\mbox{,}}j+(m-1)/2}^{k}=$$\sum _{l=0}^{m}\sum _{r=-m+1}^{m-1}d_{m{\mbox{,}}l}a_{\alpha {\mbox{,}}r{\mbox{,}}l}\left(\sum _{s=-m+1}^{m-2}f_{s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s+1}^{k-1}-\right.\right.$$\left.\left.p_{i+r{\mbox{,}}j+s}^{k-1}\right)\right){\mbox{.}}$

(B.4)

Using (B.1) and (B.2) recursively and utilizing (2.3) and (2.7) we get

${\beta }_{1}^{k}\leqslant {\left(\delta \right)}^{k}{\beta }_{1}^{0}{\mbox{.}}$

Using (B.3) and (B.4) recursively and utilizing (2.3) and (2.7) we get

${\beta }_{2}^{k}\leqslant {\left(\delta \right)}^{k}{\beta }_{2}^{0}{\mbox{.}}$

This completes the proof. □

Proof.

From (2.1) and (2.2)

$p_{i+m/2{\mbox{,}}j+m/2}^{k+1}-p_{i{\mbox{,}}j}^{k}=\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left(\sum _{r=-m+1}^{m-1}a_{1{\mbox{,}}r{\mbox{,}}l}\left(\sum _{s=-m+1}^{m-1}a_{1{\mbox{,}}s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s}^{k}-\right.\right.\right.$$\left.\left.\left.p_{i{\mbox{,}}j}^{k}\right)\right)\right){\mbox{.}}$

(C.1)

By expanding innermost summation we get

$\sum _{s=-m+1}^{m-1}a_{1{\mbox{,}}s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)=a_{1{\mbox{,}}-m+1{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j-m+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+\cdots +a_{1{\mbox{,}}-1{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+a_{1{\mbox{,}}0{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+a_{1{\mbox{,}}1{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+\cdots +a_{1{\mbox{,}}m-1{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+m-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right){\mbox{.}}$

This implies

$\sum _{s=-m+1}^{m-1}a_{1{\mbox{,}}s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)=N_{1{\mbox{,}}l}^{k}+N_{2{\mbox{,}}l}^{k}{\mbox{,}}$

where

$N_{1{\mbox{,}}l}^{k}=a_{1{\mbox{,}}0{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+a_{1{\mbox{,}}1{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+a_{1{\mbox{,}}2{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+2}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j+1}^{k}+p_{i+r{\mbox{,}}j+1}^{k}-p_{i+r{\mbox{,}}j}^{k}\right)+$$a_{1{\mbox{,}}3{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+3}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j+2}^{k}+p_{i+r{\mbox{,}}j+2}^{k}-p_{i+r{\mbox{,}}j+1}^{k}+\right.$$\left.p_{i+r{\mbox{,}}j+1}^{k}-p_{i+r{\mbox{,}}j}^{k}\right)+$$\cdots +a_{1{\mbox{,}}m-1{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+m-1}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j+m-2}^{k}+\cdots +p_{i+r{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j}^{k}\right){\mbox{,}}$

$N_{2{\mbox{,}}l}^{k}=a_{1{\mbox{,}}-1{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+a_{1{\mbox{,}}-2{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j-2}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j-1}^{k}+p_{i+r{\mbox{,}}j-1}^{k}-p_{i+r{\mbox{,}}j}^{k}\right)+$$a_{1{\mbox{,}}-3{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j-3}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j-2}^{k}+p_{i+r{\mbox{,}}j-2}^{k}-p_{i+r{\mbox{,}}j-1}^{k}+\right.$$\left.p_{i+r{\mbox{,}}j-1}^{k}-p_{i+r{\mbox{,}}j}^{k}\right)+$$\cdots +a_{1{\mbox{,}}-m+1{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j-m+1}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j-m+2}^{k}+\cdots +p_{i+r{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j}^{k}\right){\mbox{.}}$

This implies

$\sum _{s=-m+1}^{m-1}a_{1{\mbox{,}}s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)=a_{1{\mbox{,}}0{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}\left(p_{i+r{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}\left(p_{i+r{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+\left(\sum _{q=1}^{m-2}{\tilde {a}}_{1{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{1{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+r{\mbox{,}}j+q+1}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j+q}^{k}\right){\mbox{,}}$

(C.2)

where ${\textstyle {\xi }_{1{\mbox{,}}l}^{1}}$, ${\textstyle {\xi }_{1{\mbox{,}}l}^{2}}$, ${\textstyle {\tilde {a}}_{1{\mbox{,}}q{\mbox{,}}l}}$ and ${\textstyle {\tilde {\tilde {a}}}_{1{\mbox{,}}q+1{\mbox{,}}l}}$ are defined by (2.5).

Taking summation on both sides we obtain,

$\sum _{r=-m+1}^{m-1}a_{1{\mbox{,}}r{\mbox{,}}l}\left(\sum _{s=-m+1}^{m-1}a_{1{\mbox{,}}s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s}^{k}-\right.\right.$$\left.\left.p_{i{\mbox{,}}j}^{k}\right)\right)=a_{1{\mbox{,}}0{\mbox{,}}l}\sum _{r=-m+1}^{m-1}a_{1{\mbox{,}}r{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}\sum _{r=-m+1}^{m-1}a_{1{\mbox{,}}r{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}\sum _{r=-m+1}^{m-1}a_{1{\mbox{,}}r{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+\sum _{r=-m+1}^{m-1}a_{1{\mbox{,}}r{\mbox{,}}l}\left(\sum _{q=1}^{m-2}{\tilde {a}}_{1{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{1{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+r{\mbox{,}}j+q+1}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j+q}^{k}\right){\mbox{.}}$

(C.3)

Likewise by expanding summation appear on right hand side of above equation we get

$\sum _{r=-m+1}^{m-1}a_{1{\mbox{,}}r{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)={\xi }_{1{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+\left(\sum _{q=1}^{m-2}{\tilde {a}}_{1{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{1{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+q+1{\mbox{,}}j}^{k}-\right.$$\left.p_{i+q{\mbox{,}}j}^{k}\right){\mbox{,}}$

(C.4)

$\sum _{r=-m+1}^{m-1}a_{1{\mbox{,}}r{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)={\xi }_{1{\mbox{,}}l}^{3}\left(p_{i{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j-1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j-1}^{k}\right)+\left(\sum _{q=1}^{m-2}{\tilde {a}}_{1{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{1{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+q+1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i+q{\mbox{,}}j-1}^{k}\right){\mbox{,}}$

(C.5)

where ${\textstyle {\xi }_{1{\mbox{,}}l}^{3}}$ is defined by (2.5) and

$\sum _{r=-m+1}^{m-1}a_{1{\mbox{,}}r{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)={\xi }_{1{\mbox{,}}l}^{3}\left(p_{i{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j+1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j+1}^{k}\right)+\left(\sum _{q=1}^{m-2}{\tilde {a}}_{1{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{1{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+q+1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i+q{\mbox{,}}j+1}^{k}\right){\mbox{.}}$

(C.6)

Substituting (C.4), (C.5) and (C.6) in (C.3) we get

$\sum _{r=-m+1}^{m-1}a_{1{\mbox{,}}r{\mbox{,}}l}\left(\sum _{s=-m+1}^{m-1}a_{1{\mbox{,}}s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s}^{k}-\right.\right.$$\left.\left.p_{i{\mbox{,}}j}^{k}\right)\right)=N_{3{\mbox{,}}l}^{k}+$$N_{4{\mbox{,}}l}^{k}{\mbox{,}}$

where

$N_{3{\mbox{,}}l}^{k}=a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{1{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{1{\mbox{,}}l}^{3}\left(p_{i{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{1{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{1{\mbox{,}}l}^{3}\left(p_{i{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\left({\xi }_{1{\mbox{,}}l}^{2}\right)}^{2}\left(p_{i-1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j-1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{1{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j-1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{1{\mbox{,}}l}^{1}\left(p_{i-1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j+1}^{k}\right)+{\left({\xi }_{1{\mbox{,}}l}^{1}\right)}^{2}\left(p_{i+1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j+1}^{k}\right){\mbox{,}}$

$N_{4{\mbox{,}}l}^{k}=a_{1{\mbox{,}}0{\mbox{,}}l}\left(\sum _{q=1}^{m-2}{\tilde {a}}_{1{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{1{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+q+1{\mbox{,}}j}^{k}-\right.$$\left.p_{i+q{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}\left(\sum _{q=1}^{m-2}{\tilde {a}}_{1{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{1{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+q+1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i+q{\mbox{,}}j-1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}\left(\sum _{q=1}^{m-2}{\tilde {a}}_{1{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{1{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+q+1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i+q{\mbox{,}}j+1}^{k}\right)+\sum _{r=-m+1}^{m-1}a_{1{\mbox{,}}r{\mbox{,}}l}\left(\sum _{q=1}^{m-2}{\tilde {a}}_{1{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{1{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+r{\mbox{,}}j+q+1}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j+q}^{k}\right){\mbox{.}}$

Substituting it into (C.1) then by using (2.4) and (2.5) and taking norm we get

${\underset {i{\mbox{,}}j}{max}}\left\|p_{i+m/2{\mbox{,}}j+m/2}^{k+1}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right\|\leqslant \sum _{l=0}^{m}d_{m{\mbox{,}}l}\left\{\vert a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{1{\mbox{,}}l}^{2}\vert +\right.$$\left.\vert a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{1{\mbox{,}}l}^{1}\vert +\right.$$\left.\vert {\xi }_{1{\mbox{,}}l}^{2}\vert ^{2}+2\vert {\xi }_{1{\mbox{,}}l}^{2}{\xi }_{1{\mbox{,}}l}^{1}\vert +\right.$$\left.\vert {\xi }_{1{\mbox{,}}l}^{1}\vert ^{2}+\vert a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{1{\mbox{,}}l}^{4}\vert +\right.$$\left.\vert {\xi }_{1{\mbox{,}}l}^{2}{\xi }_{1{\mbox{,}}l}^{4}\vert +\right.$$\left.\vert {\xi }_{1{\mbox{,}}l}^{1}{\xi }_{1{\mbox{,}}l}^{4}\vert \right\}{\underset {i{\mbox{,}}j}{max}}\left\|{\Delta }_{i{\mbox{,}}j{\mbox{,}}1}^{k}\right\|+$$\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left\{\vert {\xi }_{1{\mbox{,}}l}^{2}{\xi }_{1{\mbox{,}}l}^{3}\vert +\right.$$\left.\vert {\xi }_{1{\mbox{,}}l}^{1}{\xi }_{1{\mbox{,}}l}^{3}\vert +\right.$$\left.\vert {\xi }_{1{\mbox{,}}l}^{3}{\xi }_{1{\mbox{,}}l}^{4}\vert \right\}{\underset {i{\mbox{,}}j}{max}}\left\|{\Delta }_{i{\mbox{,}}j{\mbox{,}}2}^{k}\right\|{\mbox{.}}$

Using notations (2.3), (2.6) and (A.1) we get

$M_{\left(1{\mbox{,}}1\right)}^{k}\leqslant {\eta }_{1}^{1}{\beta }_{1}^{k}+$${\eta }_{1}^{2}{\beta }_{2}^{k}{\mbox{.}}$

Using (3.1) we get,

$M_{\left(1{\mbox{,}}1\right)}^{k}\leqslant \left({\eta }_{1}^{1}{\beta }_{1}^{0}+\right.$$\left.{\eta }_{1}^{2}{\beta }_{2}^{0}\right){\left(\delta \right)}^{k}{\mbox{,}}$

where ${\textstyle \delta }$ is defined by (2.7). This completes the proof. □

Proof.

From (2.1) and (2.2)

$p_{i+(m+1)/2{\mbox{,}}j+m/2}^{k+1}-{\frac {1}{2}}\left(p_{i{\mbox{,}}j}^{k}+\right.$$\left.p_{i+1{\mbox{,}}j}^{k}\right)={\frac {1}{2}}\sum _{l=0}^{m}\sum _{r=-m+1}^{m-1}\sum _{s=-m+1}^{m-1}d_{m{\mbox{,}}l}a_{2{\mbox{,}}r{\mbox{,}}l}a_{1{\mbox{,}}s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\frac {1}{2}}\sum _{l=0}^{m}\sum _{r=-m+1}^{m-1}\sum _{s=-m+1}^{m-1}d_{m{\mbox{,}}l}a_{2{\mbox{,}}r{\mbox{,}}l}a_{1{\mbox{,}}s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s}^{k}-\right.$$\left.p_{i+1{\mbox{,}}j}^{k}\right){\mbox{.}}$

(D.1)

By expanding two summations in first term as we did in Lemma 3.2 after utilizing (2.5) we get

$\sum _{r=-m+1}^{m-1}\sum _{s=-m+1}^{m-1}a_{2{\mbox{,}}r{\mbox{,}}l}a_{1{\mbox{,}}s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)=N_{5{\mbox{,}}l}^{k}+N_{6{\mbox{,}}l}^{k}{\mbox{,}}$

(D.2)

where

$N_{5{\mbox{,}}l}^{k}=a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{3}\left(p_{i{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{2}\left(p_{i+1{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{3}\left(p_{i{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j-1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j-1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j+1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j+1}^{k}\right){\mbox{,}}$

$N_{6{\mbox{,}}l}^{k}=a_{1{\mbox{,}}0{\mbox{,}}l}\left(\sum _{q=1}^{m-2}{\tilde {a}}_{2{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{2{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+q+1{\mbox{,}}j}^{k}-\right.$$\left.p_{i+q{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}\left(\sum _{q=1}^{m-2}{\tilde {a}}_{2{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{2{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+q+1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i+q{\mbox{,}}j-1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}\left(\sum _{q=1}^{m-2}{\tilde {a}}_{2{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{2{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+q+1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i+q{\mbox{,}}j+1}^{k}\right)+\sum _{r=-m+1}^{m-1}a_{2{\mbox{,}}r{\mbox{,}}l}\left(\sum _{q=1}^{m-2}{\tilde {a}}_{1{\mbox{,}}q{\mbox{,}}l}-\right.$$\left.\sum _{q=-2}^{-m+1}{\tilde {\tilde {a}}}_{1{\mbox{,}}q+1{\mbox{,}}l}\right)\left(p_{i+r{\mbox{,}}j+q+1}^{k}-\right.$$\left.p_{i+r{\mbox{,}}j+q}^{k}\right){\mbox{.}}$

Similarly by expanding two summations in second term of (D.1) and utilizing (2.5), we get

$\sum _{r=-m+1}^{m-1}\sum _{s=-m+1}^{m-1}a_{2{\mbox{,}}r{\mbox{,}}l}a_{1{\mbox{,}}s{\mbox{,}}l}\left(p_{i+r{\mbox{,}}j+s}^{k}-\right.$$\left.p_{i+1{\mbox{,}}j}^{k}\right)=N_{6{\mbox{,}}l}^{k}+$$N_{7{\mbox{,}}l}^{k}{\mbox{,}}$

(D.3)

$N_{7{\mbox{,}}l}^{k}=a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+\left(a_{2{\mbox{,}}0{\mbox{,}}l}+\right.$$\left.{\xi }_{2{\mbox{,}}l}^{2}\right){\xi }_{1{\mbox{,}}l}^{2}\left(p_{i{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j+1}^{k}\right)+\left(a_{2{\mbox{,}}0{\mbox{,}}l}+\right.$$\left.{\xi }_{2{\mbox{,}}l}^{2}\right){\xi }_{1{\mbox{,}}l}^{1}\left(p_{i{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j-1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i+1{\mbox{,}}j}^{k}\right)+\left(a_{2{\mbox{,}}0{\mbox{,}}l}+\right.$$\left.{\xi }_{2{\mbox{,}}l}^{2}\right){\xi }_{1{\mbox{,}}l}^{3}\left(p_{i{\mbox{,}}j}^{k}-\right.$$\left.p_{i+1{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i+1{\mbox{,}}j}^{k}\right){\mbox{,}}$

Substituting (D.2) and (D.3) in (D.1) then after simplifying we have

$p_{i+(m+1)/2{\mbox{,}}j+m/2}^{k+1}-{\frac {1}{2}}\left(p_{i{\mbox{,}}j}^{k}+\right.$$\left.p_{i+1{\mbox{,}}j}^{k}\right)={\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left\{2N_{6{\mbox{,}}l}^{k}+\right.$$\left.N_{8{\mbox{,}}l}^{k}\right\}{\mbox{,}}$

where

$N_{8{\mbox{,}}l}^{k}=2a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}\left(a_{2{\mbox{,}}0{\mbox{,}}l}+\right.$$\left.{\xi }_{2{\mbox{,}}l}^{2}+{\xi }_{2{\mbox{,}}l}^{3}\right)\left(p_{i{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+\left\{a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{1}-\right.$$\left.{\xi }_{1{\mbox{,}}l}^{3}\left(a_{2{\mbox{,}}0{\mbox{,}}l}+\right.\right.$$\left.\left.{\xi }_{2{\mbox{,}}l}^{2}\right)\right\}\left(p_{i+1{\mbox{,}}j}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}\left(a_{2{\mbox{,}}0{\mbox{,}}l}+\right.$$\left.{\xi }_{2{\mbox{,}}l}^{2}+{\xi }_{2{\mbox{,}}l}^{3}\right)\left(p_{i{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j}^{k}\right)+2{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j-1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i{\mbox{,}}j-1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j-1}^{k}-\right.$$\left.p_{i+1{\mbox{,}}j}^{k}\right)+2{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{2}\left(p_{i-1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j+1}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i+1{\mbox{,}}j}^{k}\right)+{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{1}\left(p_{i+1{\mbox{,}}j+1}^{k}-\right.$$\left.p_{i{\mbox{,}}j+1}^{k}\right){\mbox{.}}$

Taking norm and using (2.4) and (2.5) we obtain

${\underset {i{\mbox{,}}j}{max}}\left\|p_{i+(m+1)/2{\mbox{,}}j+m/2}^{k+1}-\right.$$\left.{\frac {1}{2}}\left(p_{i{\mbox{,}}j}^{k}+p_{i+1{\mbox{,}}j}^{k}\right)\right\|\leqslant {\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left\{2\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{2}\right|+\right.$$\left.\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{1}-\right.\right.$$\left.\left.\left(a_{2{\mbox{,}}0{\mbox{,}}l}+{\xi }_{2{\mbox{,}}l}^{2}\right){\xi }_{1{\mbox{,}}l}^{3}\right|+\right.$$\left.2\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{2}\right|+\right.$$\left.\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{1}\right|+\right.$$\left.2\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{2}\right|+\right.$$\left.\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{1}\right|+\right.$$\left.2\left|a_{1{\mbox{,}}0{\mbox{,}}l}{\xi }_{2{\mbox{,}}l}^{4}\right|+\right.$$\left.2\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{4}\right|+\right.$$\left.2\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{4}\right|\right\}{\underset {i{\mbox{,}}j}{max}}\left\|{\Delta }_{i{\mbox{,}}j{\mbox{,}}1}^{k}\right\|+$${\frac {1}{2}}\sum _{l=0}^{m}d_{m{\mbox{,}}l}\left\{\left|\left(a_{2{\mbox{,}}0{\mbox{,}}l}+\right.\right.\right.$$\left.\left.\left.{\xi }_{2{\mbox{,}}l}^{2}+{\xi }_{2{\mbox{,}}l}^{3}\right){\xi }_{1{\mbox{,}}l}^{2}\right|+\right.$$\left.\left|\left(a_{2{\mbox{,}}0{\mbox{,}}l}+{\xi }_{2{\mbox{,}}l}^{2}+\right.\right.\right.$$\left.\left.\left.{\xi }_{2{\mbox{,}}l}^{3}\right){\xi }_{1{\mbox{,}}l}^{1}\right|+\right.$$\left.\left|{\xi }_{1{\mbox{,}}l}^{2}{\xi }_{2{\mbox{,}}l}^{1}\right|+\right.$$\left.\left|{\xi }_{1{\mbox{,}}l}^{1}{\xi }_{2{\mbox{,}}l}^{1}\right|+\right.$$\left.2\left|{\xi }_{2{\mbox{,}}l}^{3}{\xi }_{1{\mbox{,}}l}^{4}\right|\right\}{\underset {i{\mbox{,}}j}{max}}\left\|{\Delta }_{i{\mbox{,}}j{\mbox{,}}2}^{k}\right\|{\mbox{.}}$

Using notations (2.3), (2.6) and (A.2) we get

$M_{\left(2{\mbox{,}}1\right)}^{k}\leqslant {\eta }_{2}^{1}{\beta }_{1}^{k}+$${\eta }_{2}^{2}{\beta }_{2}^{k}{\mbox{.}}$

Using (3.1), we get

$M_{\left(2{\mbox{,}}1\right)}^{k}\leqslant \left({\eta }_{2}^{1}{\beta }_{1}^{0}+\right.$$\left.{\eta }_{2}^{2}{\beta }_{2}^{0}\right){\left(\delta \right)}^{k}{\mbox{,}}$

where ${\textstyle \delta }$ is defined by (2.7). This completes the proof. □

References

1. [1] K. Rehan, M.A. Sabri; A combined ternary 4-point subdivision scheme; Appl. Math. Comput., 276 (2016), pp. 278–283
2. [2] G. Mustafa, P. Ashraf, J. Deng; Generalized and unified families of interpolating subdivision schemes; Numer. Math.: Theory, Methods Appl., 7 (02) (2014), pp. 193–213
3. [3] F. Khan, N. Batool, M.S. Hashmi; A new approach to approximating subdivision surface using Lagrange interpolating polynomial; Sci. Int., 26 (1) (2014), pp. 41–46
4. [4] C. Loop, Smooth Subdivision Surfaces Based on Triangles, Master’s thesis, University of Utah, Department of Mathematics, 1987.
5. [5] N. Dyn, A. Gregory, D. Levin; Analysis of uniform binary subdivision schemes for curve design; Const. Approx., 7 (1991), pp. 127–147
6. [6] J. Hoschek, D. Lasser; Fundamentals of Computer Aided Geometric Design (Chapter 6); A K Peters, Wellesley, Massachusetts (1993)
7. [7] F. Cheng; Estimating subdivision depths for rational curves and surfaces; ACM Trans. Graph., 11 (2) (1992), pp. 140–151
8. [8] D. Nairn, J. Peters, D. Lutterkort; Sharp quantitative bounds on the distance between a polynomial piece and its Bézier control polygon; CAGD, 16 (1999), pp. 613–631
9. [9] U. Reif; Best bounds on the approximation of polynomials and splines by their control structure; CAGD, 17 (6) (2000), pp. 579–589
10. [10] D. Lutterkort, J. Peters; Tight linear envelopes for splines; Numer. Math., 89 (2001), pp. 735–748
11. [11] M.I. Karavelas, P.D. Kaklis, K.V. Kostas; Bounding the distance between 2D parametric Bézier curves and their control polygon; Computing, 72 (1–2) (2004), pp. 117–128
12. [12] H. Wang, Y. Guan, K. Qin; Error estimate for Doo–Sabin surfaces; Prog. Natural Sci., 12 (9) (2002), pp. 697–700
13. [13] H. Wang, K. Qin; Estimating subdivision depth of Catmull–Clark surfaces; J. Comput. Sci. Tech., 19 (5) (2004), pp. 657–664
14. [14] H. Wang, S. Hanqiu, K. Qin; Estimating recursion depth for Loop subdivision; Int. J. CAD/CAM, 4 (1) (2004), pp. 11–18
15. [15] X.M. Zeng, X.J. Chen; Computational formula of depth for Catmull–Clark subdivion surfaces; J. Comput. Appl. Math., 195 (1–2) (2006), pp. 252–262
16. [16] F. Cheng, J.H. Yong; Subdivision depth computation for Catmull–Clark subdivision surface; CAGD Appl., 3 (1–4) (2006), pp. 485–494
17. [17] G. Mustafa, F. Chen, J. Deng; Estimating error bounds for binary subdivision curves/surfaces; J. Comp. Appl. Math., 193 (2006), pp. 596–613
18. [18] G. Mustafa, J. Deng; Estimating error bounds for ternary subdivision curve/surfaces; J. Comput. Math., 24 (4) (2007), pp. 473–484
19. [19] M.S. Hashmi, G. Mustafa; Estimating error bounds for quaternary subdivision schemes; J. Math. Anal. Appl., 358 (2009), pp. 159–167
20. [20] G. Mustafa, M.S. Hashmi, F. Khan; Estimating error bounds for non-stationary binary subdivision curves/surfaces; J. Inf. Comput. Sci., 2 (3) (2007), pp. 179–190
21. [21] G. Mustafa, M.S. Hashmi; Subdivision depth computation for n-ary curves/surfaces; Vis. Comput., 26 (6–8) (2010), pp. 841–851
22. [22] G. Mustafa, M.S. Hashmi, N.A. Noshi; Estimating error bounds for tensor product binary subdivision volumetric model; Int. J. Comput. Math., 12 (83) (2006), pp. 879–903
23. [23] G. Mustafa, M.S. Hashmi; Subdivision depth computation for n-ary volumetric models; Abstract Appl. Anal. (2011), Article 203453 http://dx.doi.org/10.1155/2011/203453
24. [24] Z. Huang, J. Deng, G. Wang; A bound on the approximation of a Catmull–Clark subdivision surface by its limit mesh; CAGD, 25 (2008), pp. 457–496
25. [25] G. Mustafa, M.S. Hashmi, K.P. Akhtar; Estimating error bounds of Bajaj’s solid models and their control hexahedral meshes; Lobachevskii J. Math., 26 (2007), pp. 51–61
26. [26] G. Mustafa, M.S. Hashmi, F. Khan; Error bounds for ${\textstyle {\sqrt {3}}}$ subdivision surfaces; J. Univ. Sci. Tech. China, 36 (6) (2009), Article 253-2778(2009)06
27. [27] M. Moncayo, S. Amat; Error bounds for a class of subdivision schemes based on the two-scale refinement equation; J. Comput. Appl. Math., 236 (2) (2011), pp. 265–278
28. [28] M.S. Hashmi, G. Mustafa, F. Khan; Estimating error bounds for G. Li et al subdivision scheme; Sci. Int., 26 (1) (2014), pp. 29–34