Figure 1.
The part of polygons at $ k $th and $ (k+1) $th levels are shown by solid and dash lines respectively.
Citation: Daniel Roggen, Martin Wirz, Gerhard Tröster, Dirk Helbing. Recognition of crowd behavior from mobile sensors with pattern analysis and graph clustering methods[J]. Networks and Heterogeneous Media, 2011, 6(3): 521-544. doi: 10.3934/nhm.2011.6.521
| [1] | Shahida Bashir, Rabia Mazhar, Bander Almutairi, Nauman Riaz Chaudhry . A novel approach to study ternary semihypergroups in terms of prime soft hyperideals. AIMS Mathematics, 2023, 8(9): 20269-20282. doi: 10.3934/math.20231033 |
| [2] | Shahida Bashir, Ahmad N. Al-Kenani, Maria Arif, Rabia Mazhar . A new method to evaluate regular ternary semigroups in multi-polar fuzzy environment. AIMS Mathematics, 2022, 7(7): 12241-12263. doi: 10.3934/math.2022680 |
| [3] | Moquddsa Zahra, Dina Abuzaid, Ghulam Farid, Kamsing Nonlaopon . On Hadamard inequalities for refined convex functions via strictly monotone functions. AIMS Mathematics, 2022, 7(11): 20043-20057. doi: 10.3934/math.20221096 |
| [4] | Adnan, Waseem Abbas, Sayed M. Eldin, Mutasem Z. Bani-Fwaz . Numerical investigation of non-transient comparative heat transport mechanism in ternary nanofluid under various physical constraints. AIMS Mathematics, 2023, 8(7): 15932-15949. doi: 10.3934/math.2023813 |
| [5] | Tao Yan, Ghulam Farid, Sidra Bibi, Kamsing Nonlaopon . On Caputo fractional derivative inequalities by using strongly $ (\alpha, h-m) $-convexity. AIMS Mathematics, 2022, 7(6): 10165-10179. doi: 10.3934/math.2022565 |
| [6] | Tareq Saeed, Muhammad Adil Khan, Hidayat Ullah . Refinements of Jensen's inequality and applications. AIMS Mathematics, 2022, 7(4): 5328-5346. doi: 10.3934/math.2022297 |
| [7] | Yang Pan, Yan Liu . New classes of few-weight ternary codes from simplicial complexes. AIMS Mathematics, 2022, 7(3): 4315-4325. doi: 10.3934/math.2022239 |
| [8] | M. Zakarya, Ghada AlNemer, A. I. Saied, H. M. Rezk . Novel generalized inequalities involving a general Hardy operator with multiple variables and general kernels on time scales. AIMS Mathematics, 2024, 9(8): 21414-21432. doi: 10.3934/math.20241040 |
| [9] | Ling Zhu, Zhengjie Sun . Refinements of Huygens- and Wilker- type inequalities. AIMS Mathematics, 2020, 5(4): 2967-2978. doi: 10.3934/math.2020191 |
| [10] | Muhammad Adil Khan, Josip Pečarić, Yu-Ming Chu . Refinements of Jensen’s and McShane’s inequalities with applications. AIMS Mathematics, 2020, 5(5): 4931-4945. doi: 10.3934/math.2020315 |
The refinement schemes can be viewed as a class of iterative algorithms. The main feature of these schemes is that they use initially the rough sketch of any curve called polygon to finally produce smooth sketch also called refined sketch. Initially, a refinement scheme was introduced by de Rahm [3] in 1956. Later on, Chaikin [1] introduced the scheme for curve generation in 1974. Deslauriers and Dubuc presented the interpolating schemes for curve modeling in 1989. This triggered off the modern era for the investigation of the refinement schemes. These refinement schemes have been used for curve and surface modeling for a long time by designers, engineers, computer scientists and mathematicians. The details of these applications are presented by Farin [7].
Initially, the binary refinement schemes were introduced. These schemes have two rules to refine each edge of the polygon. These rules are same for each edge of the polygon except the initial and final edges. These rules are classified as even and odd rules. These schemes take initial sketch as an input and return the refined sketch as an output. In the next step, these schemes take previously refined sketch as an input and produce more refined sketch. Repeated application of this procedure give the smooth curve/shape. Nowadays, there are many generalizations of the binary schemes. The class of ternary refinement schemes is one of the generalization of the class of binary schemes. In this class of the schemes, three rules are used instead of two rules to refine each edge of the polygon.
The analysis of the schemes is the crucial issue. Initially, Dyn et al. [4], introduced the divided difference (DD) technique to analyze the schemes in 1987. Later on, Dyn et al. [5], extended this technique for the analysis of the class of binary schemes in 1991. The study of the limiting curves produced by the binary refinement schemes was also presented by Micchelli and Prautzch [11] in 1989. Sabin [15] in 2010, gave further insight in this technique. The further extension of Dyn et al.'s work was done by Mustafa and Zahid [12] in 2013. The cross-differences of directional DD techniques was introduced by Qu [14] in 1991. The further generalization of the DD technique has not been done so for.
Another technique for the smoothness analysis of the schemes was introduced by Dyn [6] in 2002. This technique is known as Laurent polynomial technique. This technique was used by Hassan and Dodgson [8], Hassan et al. [9], Mustafa et al. [13]. Khan and Mustafa [10], Siddiqi and Rehan [16], Zheng et al. [17] and many others to analyze their binary and ternary refinement schemes. Nowadays many authors are also using this technique. However, this technique also has some limitations and need improvement. In this technique, first a sequence of coefficients used in the refinement rules of the schemes is converted into the polynomial. Secondly, the polynomial has been factorized. In this technique, multiplication, division, factorization of the polynomials are involved. Further, the computation of inequalities and the comparison of the terms are also involved. The technique, we are going to introduce is the generalization of DD technique. In this technique, the computation of inequalities and the comparison of three terms are involved. There are three simple algebraic expressions in each inequality. Further these algebraic expressions contain only the coefficients used in the refinement rules of the schemes.
The rest of this paper is structured as follows. In Section 2, a general ternary refinement scheme and its DD schemes are introduced. Their convergence is also presented in this section. In Section 3, the deviation between successive levels of polygons produced by the ternary and its DD refinement schemes are presented. The inequalities for the analysis of ternary schemes are presented in Section 4. Applications of these inequalities are also presented in this section. Summary of the work and comparison are presented in Sections 5 and 6 respectively.
We first introduce the ternary and its first, second and third order divided differences (DD) refinement schemes. Then we present their convergence in this section.
Let $ f^{k} = \{\left (i/3^k, f^{k}_{i} \right) \in \mathbb{R}^{N}, \ i \in \mathbb{Z}, \ N \geq 2, \ k \geq 0 \} $, be a polygon at $ k $th refinement level then the $ (k+1) $th polygon $ f^{k+1} $, can be obtained by the following three refinement rules
|
$ {fk+13i=m∑j=0ρjfki+j,fk+13i+1=m∑j=0ϱjfki+j,fk+13i+2=m∑j=0σjfki+j. $
|
(2.1) |
whereas $ m > 0 $ while if $ t^{k}_{i} = i/3^{k} $ then $ \left (t^{k+1}_{3i} = t^{k}_{i}, \ f^{k+1}_{3i} \right) $, $ \left (t^{k+1}_{3i+1} = \frac{1}{3}(2t^{k}_{i}+t^{k}_{i+1}), \ f^{k+1}_{3i+1} \right) $
and $ \left (t^{k+1}_{3i+2} = \frac{1}{3}(t^{k}_{i}+2t^{k}_{i+1}), \ f^{k+1}_{3i+2} \right) $ are the points of the polygon $ f^{k+1} $.
The above rules are the affine combinations of $ f^{k}_{i} $'s so
|
$ m∑ν=0ρν=m∑ν=0ϱν=m∑ν=0σν=1. $
|
(2.2) |
The one step of the refinement procedure is shown in Figure 1. The repeated application of these rules is known as ternary refinement scheme.
The first, second and third order divided difference (DD) ternary refinement schemes (TRS) are presented in this section.
Lemma 2.1. Let $ f^{k} = \{\left (i/3^k, f^{k}_{i} \right) \} $ be a polygon of TRS at $ k $th refinement level and $ d^{[1] k}_{j} = 3^{k}(f^{k}_{j+1}-f^{k}_{j}) $ be the first divided difference then the first order DD TRS is defined as
|
$ {d[1](k+1)3i=3m−1∑μ=0{μ∑ν=0(ρμ−ν−ϱμ−ν)d[1]ki+μ},d[1](k+1)3i+1=3m−1∑μ=0{μ∑ν=0(ϱμ−ν−σμ−ν)d[1]ki+μ},d[1](k+1)3i+2=3m∑μ=0{μ∑ν=0(σμ−ν−ρμ−ν−1)d[1]ki+μ}. $
|
(2.3) |
Proof. Since the first order DD is defined as
|
$ d[1]kν=3k(fkν+1−fkν), $
|
(2.4) |
therefore by (2.1), we get
|
$ d[1](k+1)3i=3k+1{(ϱ0−ρ0)fki+(ϱ1−ρ1)fki+1+(ϱ2−ρ2)fki+2+…+(ϱm−1−ρm−1)fki+m−1+(ϱm−ρm)fki+m}. $
|
(2.5) |
Now consider the linear combination
|
$ d[1](k+1)3i=y0d[1]ki+y1d[1]ki+1+y2d[1]ki+2+…+ym−1d[1]ki+(m−1). $
|
(2.6) |
The goal is to find the unknown $ y_{0}, \cdots, y_{m-1} $. It can be written as
|
$ d[1](k+1)3i=3k{−y0fki+(y0−y1)fki+1+(y1−y2)fki+2+…+(ym−3−ym−2)fkm−2+(ym−2−ym−1)fki+(m−1)+ym−1fki+m}. $
|
(2.7) |
Comparing (2.5) and (2.7), we get
|
$ y0=3(ρ0−ϱ0),y1=3(ρ0−ϱ0)+3(ρ1−ϱ1),y2=3(ρ0−ϱ0)+3(ρ1−ϱ1)+3(ρ2−ϱ2),⋮ym−1=3(ρ0−ϱ0)+3(ρ1−ϱ1)+⋯+3(ρm−1−ϱm−1). $
|
Substituting in (2.6), we get
|
$ d[1](k+1)3i=3[(ρ0−ϱ0)d[1]ki+{(ρ0−ϱ0)+(ρ1−ϱ1)}d[1]ki+1+{(ρ0−ϱ0)+(ρ1−ϱ1)+(ρ2−ϱ2)}d[1]ki+2+…+{(ρ0−ϱ0)+(ρ1−ϱ1)+…+(ρm−1−ϱm−1)}d[1]ki+(m−1)]. $
|
This implies
|
$ d[1](k+1)3i=3m−1∑μ=0{μ∑ν=0(ρμ−ν−ϱμ−ν)d[1]ki+μ}. $
|
Similarly, we get
|
$ d[1](k+1)3i+1=3m−1∑μ=0{μ∑ν=0(ϱμ−ν−σμ−ν)d[1]ki+μ}, $
|
and
|
$ d[1](k+1)3i+2=3m∑μ=0{μ∑ν=0(σμ−ν−ρμ−ν−1)d[1]ki+μ}. $
|
This completes the proof. By adopting the similar procedure, we get the following results.
Lemma 2.2. Let $ f^{k} = \{\left (i/3^k, f^{k}_{i} \right)\} $ be a polygon of TRS at $ k $th refinement level and
|
$ d[2]kj=32k(2!)−1(fkj−1−2fkj+fkj+1) $
|
be the second order divided difference then the second order DD TRS is defined as
|
$ {d[2](k+1)3i=32m−1∑μ=0[μ∑ν=0{(ν+1)σμ−ν+νϱμ−ν−2νρμ−ν}d[2]ki+μ],d[2](k+1)3i+1=32m−2∑μ=0[μ∑ν=0{(ν+1)(ρμ−ν+σμ−ν−2ϱμ−ν)}d[2]ki+μ+1],d[2](k+1)3i+2=32m−1∑μ=0[μ∑ν=0{νρμ−ν+(ν+1)ϱμ−ν−(2ν+2)σμ−ν}d[2]ki+μ+1]. $
|
(2.8) |
Lemma 2.3. Let $ f^{k} = \{\left (i/3^k, f^{k}_{i} \right)\} $ be a polygon of TRS at $ k $th refinement level and
|
$ d[3]k)j=33k(3!)−1(−fkj−1+3fkj−3fkj+1+fkj+2) $
|
be the third order divided difference then the third order DD TRS is defined as
|
$ {d[3](k+1)3i=33m−2∑μ=0[μ∑ν=0{(ν+1)σμ−ν−3ν(ν+1)2(ρμ−ν−ϱμ−ν)}d[3]ki+μ],d[3](k+1)3i+1=33m−2∑μ=0[μ∑ν=0{(ν+1)ρμ−ν−3(ν+1)(ν+2)2(ϱμ−ν−σμ−ν)}d[3]ki+μ+1],d[3](k+1)3i+2=33m−2∑μ=0[μ∑ν=0{3ν(ν+1)2ρμ−ν+(ν+1)ϱμ−ν−3(ν+1)(ν+2)2σμ−ν}d[3]ki+μ+1]. $
|
(2.9) |
The convergence of first, second and third order divided difference (DD) ternary refinement schemes (TRS) is presented in this section. Throughout the paper, $ \pi{[0, n]} $ denotes the set of continuous functions on the closed and bounded interval $ [0, n] $.
Lemma 2.4. Let $ f^{k} = \left\{\left (i/3^k, f^{k}_{i} \right)\right\} $ be a polygon of TRS at $ k $th refinement level and $ d^{[1] k} = \left\{\left (i/3^k, d^{[1] k}_{i} \right) \right\} $ be a polygon of first order DD scheme. If $ lim_{k\rightarrow\infty} d^{[1] k} = d^{[1] } \in \pi{[0, n]} $, and $ f $ is the limiting curve/shape produced by TRS then $ d^{[1] } = f' $.
Proof. Bernstein polynomial for $ x \in [0, n] $ with data values $ {f_{i}^{k}} $ is
|
$ Bk(x)=s∑i=0(si)(xn)i(1−xn)s−ifki. $
|
Its first derivative is
|
$ B′k(x)=s∑i=0(si)in(xn)i−1(1−xn)s−ifki+s∑i=0(si)(xn)i(s−i)(−1n)(1−xn)s−i−1fki. $
|
(2.10) |
This implies
|
$ B′k(x)=sns−1∑i=0(s−1i)(xn)i(1−xn)s−i−1(fki+1−fki). $
|
For $ s = 3^kn $, we get
|
$ B′k(x)=s−1∑i=0(s−1i)(xn)i(1−xn)s−i−13k(fki+1−fki). $
|
This again implies
|
$ B′k(x)=s−1∑i=0(s−1i)(xn)i(1−xn)s−i−1d[1]ki. $
|
Since the Bernstien polynomials are uniformly convergent therefore $ lim_{k\rightarrow\infty}B_k = f $ and $ lim_{k\rightarrow\infty}B'_k = d^{[1] } $ on $ [0, n] $. So $ f' = d^{[1] } \in \pi{[0, n]} $. Hence the proof.
Lemma 2.5. Let $ f^{k} = \left\{\left (i/3^k, f^{k}_{i} \right)\right\} $ and $ d^{[2] k} = \left\{\left (i/3^k, d^{[2] k}_{i} \right) \right\} $ be the polygons of TRS and its second order DD schemes respectively. If $ lim_{k\rightarrow\infty} d^{[2] k} = d^{[2] } \in \pi{[0, n]} $, and $ f $ is the limiting curve produced by TRS then $ d^{[2] } = f'' $.
Proof. Take the derivative of (2.10)
|
$ B″k(x)=1n2{s(s−1)s∑i=2(s−2)!(i−2)!(s−i)! (xn)i−2(1−xn)s−ifki−2s(s−1)s−1∑i=1(s−2)!(i−1)!(s−i−1)! (xn)i−1(1−xn)s−i−1fki +s(s−1)s−2∑i=0(s−2)!i!(s−i−2)!(xn)i(1−xn)s−i−2fki}. $
|
(2.11) |
This implies
|
$ B″k(x)=s(s−1)n2{s−2∑i=0(s−2)!(i)!(s−i−2)! (xn)i(1−xn)s−i−2×(fki+2−2fi+1+fki)}. $
|
Since $ s = 3^{k}n $ therefore $ \frac{s(s-1)}{n^2} = 3^{2k}2^{-1} $, so we get
|
$ B″k(x)=32k2−1{s−2∑i=0(s−2)!(i)!(s−i−2)! (xn)i(1−xn)s−i−2×(fki+2−2fi+1+fki)}. $
|
This implies
|
$ B″k(x)=s−2∑i=0{(s−2)!(i)!(s−i−2)! (xn)i(1−xn)s−i−2}d[2]ki+1, $
|
where $ d^{[2] k}_{i+1} $ = $ 3^{2k}(2!)^{-1}(f_{i+2}^{k}-2f_{i+1}^{k}+f_{i}^{k}). $
Again the uniform convergence of the Bernstien polynomials implies $ lim_{k\rightarrow\infty}B^{''}_k = d^{[2] } $ and $ lim_{k\rightarrow\infty}B_k = f $. Therefore when $ k\rightarrow\infty $ then $ d^{[2] } $ converges uniformly to $ f^{''} $ on $ [0, n] $. This concludes $ d^{[2] } = f^{''} \in \pi{[0, n]} $. Hence the proof.
Lemma 2.6. Let $ f^{k} = \{\left (i/3^k, f^{k}_{i} \right)\} $ and $ d^{[3] k)} = \left\{\left (i/3^k, d^{[3] k}_{i} \right) \right\} $ be the polygons of TRS and its third order DD schemes respectively. If $ lim_{k\rightarrow\infty} d^{[3] k} = d^{[3] } \in \pi{[0, n]} $ then $ d^{[3] } = f''' $.
Proof. Now take the derivative of (2.11), then
|
$ B‴k(x)=1n3s∑i=3s(s−1)(s−2)(s−3)!(i−3)!(s−i)!(xn)i−3(1−xn)s−ifki−3n3s−1∑i=2s(s−1)(s−2)(s−3)!(i−2)!(s−i−1)!(xn)i−2(1−xn)s−i−1fki+3n3s−2∑i=1s(s−1)(s−2)(s−3)!(i−1)!(s−i−2)!(xn)i−1(1−xn)s−i−2fki−1n3s−3∑i=0s(s−1)(s−2)(s−3)!i!(s−i−3)!(xn)i(1−xn)s−i−3fki. $
|
Since, $ s = 3^{k}n $, then
|
$ B‴k(x)=33k(3!)−1s−3∑i=0(s−3i)(xn)i(1−xn)s−i−3×(−fki+3fki+1−3fki+2+fki+3). $
|
This implies
|
$ B‴k(x)=s−3∑i=0(s−3i)(xn)i(1−xn)s−i−3d[3]ki+1, $
|
where
|
$ d[3]ki+1=33k(3!)−1(−fki+3fki+1−3fki+2+fki+3). $
|
This implies $ B^{'''}_k\rightarrow d^{[3] } $ and $ B_k\rightarrow f. $ This implies that for $ k\rightarrow\infty $ the $ d^{[3] } $ converges uniformly to $ f^{'''} $ on $ [0, n] $. This concludes that $ d^{[3] } = f^{'''} \in \pi{[0, n]} $. Hence the proof.
We first introduce the inequalities to compute the deviation between two consecutive points at the same refinement level then we introduce the inequalities to compute the deviation between successive levels of polygons produced by ternary and its DD refinement schemes.
Lemma 3.1. If $ f^{0} = \{\left (i/3^0, f^{0}_{i} \right)\} $ is the initial polygon and $ f^{k+1} = \{\left (i/3^{k+1}, f^{k+1}_{i} \right)\} $ is the polygon obtained by TRS at $ (k+1) $th refinement level. If $ \varpi < 1 $ then the deviation between two consecutive points at $ (k+1) $th level is
|
$ maxi‖fk+1i+1−fk+1i‖≤(ϖ)k+1maxi‖f0i+1−f0i‖, $
|
(3.1) |
|
$ ϖ=max{ϖ1,ϖ2,ϖ3}<1, $
|
(3.2) |
|
$ {ϖ1=m−1∑μ=0|μ∑ν=0(ρμ−ν−ϱμ−ν)|,ϖ2=m−1∑μ=0|μ∑ν=0(ϱμ−ν−σμ−ν)|,ϖ3=m∑μ=0|μ∑ν=0(σμ−ν−ρμ−ν−1)|. $
|
(3.3) |
Proof. From (2.1), we get
|
$ fk+13i+1−fk+13i=m∑ν=0ϱνfki+ν−m∑ν=0ρνfki+ν=m∑ν=0(ϱν−ρν)fki+ν. $
|
This further implies
|
$ fk+13i+1−fk+13i=[(ρ0−ϱ0)(fki+1−fki)+{(ρ0−ϱ0)+(ρ1−ϱ1)}(fki+2−fki+1)+{(ρ0−ϱ0)+(ρ1−ϱ1)+(ρ2−ϱ2)}(fki+3−fki+2)+…+{(ρ0−ϱ0)+(ρ1−ϱ1)+…+(ρm−1−ϱm−1)}(fki+m−fki+m−1)+{(ϱ0−a0)+(ϱ1−ρ1)+…+(ϱm−ρm)}fki+m]. $
|
This leads to
|
$ fk+13i+1−fk+13i=m−1∑μ=0{μ∑ν=0(ρμ−ν−ϱμ−ν)}(fki+μ+1−fki+μ)+m∑ν=0(ϱν−ρν)fki+m. $
|
Since by (2.2), $ \sum\limits_{\nu = 0}^m\left(\varrho_{\nu}-\rho_{\nu}\right) = 0 $, then
|
$ fk+13i+1−fk+13i=m−1∑μ=0{μ∑ν=0(ρμ−ν−ϱμ−ν)(fki+μ+1−fki+μ)}. $
|
By taking maximum norm, we get
|
$ ‖fk+13i+1−fk+13i‖≤ϖ1maxi‖fki+1−fki‖, $
|
(3.4) |
where
|
$ ϖ1=m−1∑μ=0|μ∑ν=0(ρμ−ν−ϱμ−ν)|. $
|
Using (2.1) and similar procedure as above, we get
|
$ ‖fk+13i+2−fk+13i+1‖≤ϖ2maxi‖fki+1−fki‖, $
|
(3.5) |
where
|
$ ϖ2=m−1∑μ=0|μ∑ν=0(ϱμ−ν−σμ−ν)|. $
|
and
|
$ ‖fk+13i+3−fk+13i+2‖≤ϖ3maxi‖fki+1−fki‖, $
|
(3.6) |
where
|
$ ϖ3=m∑μ=0|μ∑ν=0(σμ−ν−ρμ−ν−1)|. $
|
Combining (3.4), (3.5) and (3.6), it proceeds as
|
$ maxi‖fk+1i+1−fk+1i‖≤ϖmaxi‖fki+1−fki‖, $
|
where
|
$ ϖ=max{ϖ1,ϖ2,ϖ3}. $
|
This concludes
|
$ maxi‖fk+1i+1−fk+1i‖≤(ϖ)k+1maxi‖f0i+1−f0i‖. $
|
This completes the proof.
Theorem 3.2. If $ f^{0} = \{\left (i/3^0, f^{0}_{i} \right)\} $ is the initial polygon and $ f^{k+1} = \{\left (i/3^{k+1}, f^{k+1}_{i} \right)\} $ is the polygon obtained by TRS at $ (k+1) $th refinement level. If $ \varpi^* < 1 $ then the deviation between two successive polygons at $ k $th and $ (k+1) $th levels is
|
$ ‖fk+1−fk‖∞≤ϖ∗maxi‖fki+1−fki‖, $
|
(3.7) |
where
|
$ ϖ∗=max{ϖ4,ϖ5,ϖ6}, $
|
(3.8) |
|
$ {ϖ4=m−1∑μ=0|1−μ∑ν=0ρμ−ν|,ϖ5=|23−ϱ0|+m−1∑μ=1|1−μ∑ν=0ϱμ−ν|,ϖ6=|13−σ0|+m−1∑μ=1|1−μ∑ν=0σμ−ν|. $
|
(3.9) |
Proof. Since the maximum deviation between $ f^{k+1} $ and $ f^{k} $ occurs at the diadic values $ t^{k+1}_{3i} = t^{k}_{i} $, $ t^{k+1}_{3i+1} = \frac{1}{3}(2t^{k}_{i}+t^{k}_{i+1}) $ and $ t^{k+1}_{3i+2} = \frac{1}{3}(t^{k}_{i}+2t^{k}_{i+1}) $ respectively, therefore
|
$ ‖fk+1−fk‖∞≤max{Z1k,Z2k,Z3k}, $
|
(3.10) |
where
|
$ {Z1k=maxi‖fk+13i−fki‖,Z2k=maxi‖fk+13i+1−13(2fki+fki+1)‖,Z3k=maxi‖fk+13i+2−13(fki+2fki+1)‖. $
|
(3.11) |
From (2.1), we obtain
|
$ fk+13i−fki=m∑ν=0ρνfki+ν−fki. $
|
Since by (2.1), $ \sum\limits_{\nu = 0}^{m}\rho_{\nu}-1 = 0 $, then
|
$ fk+13i−fki=m−1∑μ=0(1−μ∑ν=0ρμ−ν)(fki+μ+1−fki+μ). $
|
Taking norm, we get
|
$ ‖fk+13i−fki‖≤ϖ4maxi‖fki+1−fki‖, $
|
(3.12) |
where
|
$ ϖ4=m−1∑μ=0|1−μ∑ν=0ρμ−ν|. $
|
Using (2.1) and similar procedure as above, we get
|
$ ‖fk+13i+1−(23fki+13fki+1)‖≤ϖ5maxi‖fki+1−fki‖, $
|
(3.13) |
where
|
$ ϖ5=|23−ϱ0|+m−1∑μ=1|1−μ∑ν=0ϱμ−ν|. $
|
|
$ ‖fk+13i+2−(13fki+23fki+1)‖≤ϖ6maxi‖fki+1−fki‖, $
|
(3.14) |
where
|
$ ϖ6=|13−σ0|+m−1∑μ=1|1−μ∑ν=0σμ−ν|. $
|
From (3.10)-(3.14), we get
|
$ ‖fk+1−fk‖∞≤ϖ∗maxi|fki+1−fki|, $
|
where
|
$ ϖ∗=max{ϖ4,ϖ5,ϖ6}. $
|
Hence the proof.
Lemma 3.3. If $ d^{[1] 0} = \{\left (i/3^0, d^{[1] 0}_{i} \right)\} $ is the initial polygon and $ d^{[1] (k+1)} = $
$ \left\{\left (i/3^{k+1}, d^{[1] (k+1)}_{i} \right) \right\} $ is the polygon obtained by first order DD TRS at $ (k+1) $th refinement level. If $ \varpi^{**} < 1 $ and
|
$ {c1=m−1∑ν=0(m−ν)(2ϱν−σν−ρν)=0,c2=m∑ν=0{(2ν+1)σm−ν−(m−ν)(ρν+ϱν)}=0,c3=m∑ν=0{2νρm−ν−νϱm−ν−(ν+1)σm−ν}=0, $
|
(3.15) |
then the deviation between two consecutive points at $ (k+1) $th level is
|
$ maxi‖d[1](k+1)i+1−d[1](k+1)i‖≤(ϖ∗∗)k+1maxi‖d[1]0i+1−d[1]0i‖, $
|
(3.16) |
where
|
$ ϖ∗∗=max{ϖ∗1,ϖ∗2,ϖ∗3}, $
|
(3.17) |
|
$ {ϖ∗1=3m−2∑μ=0|μ∑ν=0(ν+1)(ρμ−ν−2ϱμ−ν+σμ−ν)|,ϖ∗2=3m−1∑μ=0|μ∑ν=0{(ν+1)ϱμ−ν−(2ν+2)σμ−ν+νρμ−ν}|,ϖ∗3=3m−1∑μ=0|μ∑ν=0{(ν+1)σμ−ν−2νρμ−ν+νϱμ−ν}|. $
|
(3.18) |
Proof. Using (2.3) and proceeding similarly as in Lemma 3.1, we get
If, $ c_{1} = \sum\limits_{\nu = 0}^{m-1}(m-\nu)(2\varrho_{\nu}-\sigma_{\nu}-\rho_{\nu}) = 0, $ then
|
$ ‖d[1](k+1)3i+1−d[1](k+1)3i‖≤ϖ∗1maxi‖d[1]ki+1−d[1]ki‖, $
|
(3.19) |
where
|
$ ϖ∗1=3m−2∑μ=0|μ∑ν=0(ν+1)(ρμ−ν−2ϱμ−ν+σμ−ν)|. $
|
Using (2.3) and similar procedure as above, we get
$ c_{2} = \sum\limits_{\nu = 0}^{m}\left\{(2\nu+1)\sigma_{m-\nu}-(m-\nu)(\rho_{\nu}+\varrho_{\nu})\right\} = 0, $
|
$ ‖d[1](k+1)3i+2−d[1](k+1)3i+1‖≤ϖ∗2maxi‖d[1]ki+1−d[1]ki‖. $
|
(3.20) |
where
|
$ ϖ∗2=3m−1∑μ=0|μ∑ν=0{(ν+1)ϱμ−ν−(2ν+2)σμ−ν+νρμ−ν}|. $
|
And
$ c_{3} = \sum\limits_{\nu = 0}^{m}\left\{2\nu\rho_{m-\nu}-\nu\varrho_{m-\nu}-(\nu+1)\sigma_{m-\nu}\right\} = 0, $
|
$ ‖d[1](k+1)3i+3−d[1](k+1)3i+2‖≤ϖ∗3maxi‖d[1]ki+1−d[1]ki‖, $
|
(3.21) |
where
|
$ ϖ∗3=3m−1∑μ=0|μ∑ν=0{(ν+1)σμ−ν−2νρμ−ν+νϱμ−ν}|. $
|
Combining Eqs (3.19), (3.20) and (3.21), we get
|
$ maxi‖d[1](k+1)i+1−d[1](k+1)i‖≤ϖ∗∗maxi‖d[1]ki+1−d[1]ki‖, $
|
whereas
|
$ ϖ∗∗=max{ϖ∗1,ϖ∗2,ϖ∗3}. $
|
This implies
|
$ maxi‖d[1](k+1)i+1−d[1](k+1)i‖≤(ϖ∗∗)k+1maxi‖d[1]0i+1−d[1]0i‖. $
|
This completes the proof.
Theorem 3.4. If $ d^{[1] 0} = \left\{\left (i/3^0, d^{[1] 0}_{i} \right) \right\} $ is the initial polygon and $ d^{[1] (k+1)} = $
$ \left\{\left (i/3^{k+1}, d^{[1] (k+1)}_{i} \right) \right\} $ is the polygon obtained by first order DD TRS at $ (k+1) $th refinement level. If $ \varpi^{***} < 1 $ and
|
$ {c4=−13+m∑ν=1ν(ρm−ν−ϱm−ν)=0,c5=−13+m∑ν=1ν(ϱm−ν−σm−ν)=0,c6=−13+m∑ν=0{(ν+1)σm−ν−νρm−ν}=0, $
|
(3.22) |
then the deviation between two successive polygons at $ k $th and $ (k+1) $th levels is
|
$ ‖d[1](k+1)−d[1]k‖∞≤ϖ∗∗∗maxi‖d[1]ki+1−d[1]ki‖, $
|
(3.23) |
where
|
$ ϖ∗∗∗=max{ϖ∗4,ϖ∗5,ϖ∗6}, $
|
(3.24) |
|
$ {ϖ∗4=3m−2∑μ=0|13+μ∑ν=0{(ν+1)(ϱμ−ν−ρμ−ν)}|,ϖ∗5=3|232−ϱ0+σ0|+3m−2∑μ=1|13+μ∑ν=0{(ν+1)(σμ−ν−ϱμ−ν)}|,ϖ∗6=3|132−σ0|+3m−1∑μ=1|13+μ∑ν=0(νρμ−ν−(ν+1)σμ−ν)|. $
|
(3.25) |
Proof. Since the maximum deviation between $ d^{[1] (k+1)} $ and $ d^{[1] k} $ occurs at the diadic values $ t^{k+1}_{3i} = t^{k}_{i} $, $ t^{k+1}_{3i+1} = \frac{1}{3}(2t^{k}_{i}+t^{k}_{i+1}) $ and $ t^{k+1}_{3i+2} = \frac{1}{3}(t^{k}_{i}+2t^{k}_{i+1}) $ respectively, therefore
|
$ ‖d[1](k+1)−d[1]k‖∞≤max{Z4k,Z5k,Z6k}, $
|
(3.26) |
where
|
$ {Z4k=maxi‖d[1](k+1)3i−d[1]ki‖,Z5k=maxi‖d[1](k+1)3i+1−13(2d[1]ki+d[1]ki+1)‖,Z6k=maxi‖d[1](k+1)3i+2−13(d[1]ki+2d[1]ki+1)‖. $
|
(3.27) |
By (2.3), we get
|
$ d[1](k+1)3i−d[1]ki=3m−1∑μ=0{μ∑ν=0(ρμ−ν−ϱμ−ν)d[1]ki+μ}−d[1]ki. $
|
This leads to
|
$ d[1](k+1)3i−d[1]ki=3[m−2∑μ=0{13+μ∑ν=0(ν+1)(ϱμ−ν−ρμ−ν)(d[1]ki+μ+1−d[1]ki+μ+1)}+{−13+m∑ν=1ν(ρm−ν−ϱm−ν)}d[1]ki+m−1]. $
|
If, $ c_{4} = -\frac{1}{3}+\sum\limits_{\nu = 1}^{m}\nu(\rho_{m-\nu}-\varrho_{m-\nu}) = 0, $ taking norm we get
|
$ ‖d[1](k+1)3i−d[1]ki‖≤ϖ∗4maxi‖d[1]ki+1−d[1]ki‖, $
|
(3.28) |
where,
|
$ ϖ∗4=3m−2∑μ=0|13+μ∑ν=0{(ν+1)(ϱμ−ν−ρμ−ν)}|. $
|
Using (2.3) and similar procedure as above, we get
$ c_{5} = -\frac{1}{3}+\sum\limits_{\nu = 1}^{m}\nu(\varrho_{m-\nu}-\sigma_{m-\nu}) = 0, $
|
$ ‖d[1](k+1)3i+1−(23d[1]ki+13d[1]ki+1)‖≤ϖ∗5maxi‖d[1]ki+1−d[1]ki‖, $
|
(3.29) |
where
|
$ ϖ∗5=3|232−ϱ0+σ0|+3m−2∑μ=1|13+μ∑ν=0{(ν+1)(σμ−ν−ϱμ−ν)}|. $
|
And
$ c_{6} = -\frac{1}{3}+\sum\limits_{\nu = 0}^{m}\{(\nu+1)\sigma_{m-\nu}-\nu\rho_{m-\nu}\} = 0, $
|
$ maxi‖ˆdk+13i+2−(13ˆdki+23ˆdki+1)‖≤ϖ∗6maxi‖d[1]ki+1−d[1]ki‖, $
|
(3.30) |
where
|
$ ϖ∗6=3|132−σ0|+3m−1∑μ=1|13+μ∑ν=0(νρμ−ν−(ν+1)σμ−ν)|. $
|
From (3.26)-(3.30)
|
$ ‖d[1](k+1)−d[1]k‖∞≤ϖ∗∗∗maxi‖d[1]ki+1−d[1]ki‖, $
|
whereas
|
$ ϖ∗∗∗=max{ϖ∗4,ϖ∗5,ϖ∗6}. $
|
Hence the proof.
Lemma 3.5. If $ d^{[2] 0} = \left\{\left (i/3^0, d^{[2] 0}_{i} \right) \right\} $ is the initial polygon and $ d^{[2] (k+1)} = $
$ \left \{\left (i/3^{k+1}, d^{[2] (k+1)}_{i} \right)\right\} $ is the polygon obtained by second order DD TRS at $ (k+1) $th refinement level. If $ \vartheta < 1 $ and
|
$ {χ1=m−1∑ν=0{3ν(ν+1)2(ρm−ν−1−ϱm−ν−1)−(ν+1)σm−ν−1}=0,χ2=m−1∑ν=0{(ν+1)(3ν+2)2ϱm−1−ν−(ν+1)(3ν+4)2σm−1−ν}=0,χ3=m−1∑ν=0{3(ν+1)(ν+2)2σm−1−ν−(ν+1)ϱm−1−ν−3ν(ν+1)2ρm−1−ν}=0, $
|
(3.31) |
then the deviation between two consecutive points at $ (k+1) $th level is
|
$ maxi‖d[2](k+1)i+1−d[2](k+1)i‖≤(ϑ)k+1maxi‖d[2]0i+1−d[2]0i‖, $
|
(3.32) |
where
|
$ ϑ=max{ϑ1,ϑ2,ϑ3}, $
|
(3.33) |
|
$ {ϑ1=32m−2∑μ=0|μ∑ν=0{(ν+1)σμ−ν+3ν(ν+1)2(ϱμ−ν−ρμ−ν)}|,ϑ2=32m−2∑μ=0|μ∑ν=0{(ν+1)ρμ−ν+3(ν+1)(ν+2)2(σμ−ν−ϱμ−ν)}|,ϑ3=32m−2∑μ=0|μ∑ν=0{3ν(ν+1)2ρμ−ν+(ν+1)ϱμ−ν−3(ν+1)(ν+2)2σμ−ν}|. $
|
(3.34) |
Theorem 3.6. If $ d^{[2] 0} = \left\{\left (i/3^0, d^{[2] 0}_{i} \right)\right\} $ is the initial polygon and $ d^{[2] (k+1)} = $
$ \left\{\left (i/3^{k+1}, d^{[2] (k+1)}_{i} \right)\right\} $ is the polygon obtained by second order DD TRS at $ (k+1) $th refinement level. If $ \vartheta^{*} < 1 $ and
|
$ {χ4=−132+m−1∑ν=0[(ν+1)2{νϱm−1−ν+(ν+2)σm−1−ν−2νρm−1−ν}]=0,χ5=−132+m−1∑ν=1[ν(ν+1)2{ρm−ν−1+σm−ν−1−2ϱm−ν−1}]=0,χ6=−132+m∑ν=1{ν(ν+1)2ϱm−ν−ν(ν+1)σm−ν+ν(ν−1)2ρm−ν}=0, $
|
(3.35) |
then the deviation between two successive polygons at $ k $th and $ (k+1) $th levels is
|
$ ‖d[2](k+1)−d[2]k‖∞≤ϑ∗maxi‖d[2]ki+1−d[2]ki‖, $
|
(3.36) |
where
|
$ ϑ∗=max{ϑ4,ϑ5,ϑ6}, $
|
(3.37) |
|
$ {ϑ4=32m−2∑μ=0|132+μ∑ν=0{ν(ν+1)ρμ−ν−ν(ν+1)2ϱμ−ν−(ν+1)(ν+2)2σμ−ν}|,ϑ5=32|233|+32m−2∑μ=1|19+μ∑ν=1{ν(ν+1)2(2ϱμ−ν−ρμ−ν−σμ−ν)}|,ϑ6=32|133|+32m−1∑μ=1|132+μ∑ν=1{ν(ν+1)σμ−ν−ν(ν+1)2ϱμ−ν−ν(ν−1)2ρμ−ν}|. $
|
(3.38) |
Lemma 3.7. If $ d^{[3] 0} = \left\{\left (i/3^0, d^{[3] 0}_{i} \right)\right\} $ is the initial polygon and $ d^{[3] (k+1)} = $
$ \left\{\left (i/3^{k+1}, d^{[3] (k+1)}_{i} \right)\right\} $ is the polygon obtained by third order DD TRS at $ (k+1) $th refinement level. If $ \vartheta^{**} < 1 $ and
|
$ {χ7=m−2∑ν=0[(ν+1)(ν+2)2{(ν+1)ρm−ν−2−(2ν+3)ϱm−ν−2+(ν+2)σm−ν−2}]=0,χ8=m−2∑ν=0[(ν+1)(ν+2){(ν−1)2ρm−ν−2+(ν+4)2ϱm−ν−2−(ν+3)σm−ν−2}]=0,χ9=m−2∑ν=0[(ν+1)(ν+2){−νρm−ν−2+(ν−1)2ϱm−ν−2+(ν+4)2σm−ν−2}]=0, $
|
(3.39) |
then the deviation between two consecutive points at $ (k+1) $th level is
|
$ maxi‖d[3](k+1)i+1−d[3](k+1)i‖≤(ϑ∗∗)k+1maxi‖d[3]0i+1−d[3]0i‖, $
|
(3.40) |
where
|
$ ϑ∗∗=max{ϑ7,ϑ8,ϑ9}, $
|
(3.41) |
|
$ {ϑ7=33m−2∑μ=0|μ∑ν=0{ν(ν+1)(ν+2)ϱμ−ν−ν(ν+1)(ν+3)2ρμ−ν−(ν−1)(ν+1)(ν+2)2σμ−ν}|,ϑ8=33m−3∑μ=0|μ∑ν=0{−(ν−1)(ν+1)(ν+2)2ρμ−ν−(ν+1)(ν+2)(ν+4)2ϱμ−ν+(ν+1)(ν+2)(ν+3)σμ−ν}|,ϑ9=33m−3∑μ=0|μ∑ν=0{ν(ν+1)(ν+2)ρμ−ν−(ν−1)(ν+1)(ν+2)2ϱμ−ν−(ν+1)(ν+2)(ν+4)2σμ−ν}|. $
|
(3.42) |
Theorem 3.8. If $ d^{[3] 0} = \left\{\left (i/3^0, d^{[3] 0}_{i} \right)\right\} $ is the initial polygon and $ d^{[3] (k+1)} = \left\{\left (i/3^{k+1}, d^{[3] (k+1)}_{i} \right)\right\} $ is the polygon obtained by third order DD TRS at $ (k+1) $th refinement level. If $ \vartheta^{***} < 1 $ and
|
$ {χ10=−133+m−2∑ν=0[(ν+1)(ν+2)2{σm−2−ν+νϱm−2−ν−νρm−2−ν}]=0,χ11=−133+m−2∑ν=0[(ν+1)(ν+2)2{ρm−ν−2−(ν+3)ϱm−ν−2+(ν+3)σm−ν−2}]=0,χ12=−133+m−2∑ν=0[(ν+1)(ν+2)2{ϱm−ν−2−(ν+3)σm−ν−2+νρm−ν−2}]=0, $
|
(3.43) |
then the deviation between two successive polygons at $ k $th and $ (k+1) $th levels is
|
$ ‖d[3](k+1)−d[3]k‖∞≤ϑ∗∗∗maxi‖d[3]ki+1−d[3]ki‖, $
|
(3.44) |
where
|
$ ϑ∗∗∗=max{ϑ10,ϑ11,ϑ12}, $
|
(3.45) |
|
$ {ϑ10=33m−3∑μ=0|133+μ∑ν=0{(ν+1)(ν+2)2(νρμ−ν−νϱμ−ν−σμ−ν)}|,ϑ11=33|234|+33m−2∑μ=1|133+μ∑ν=1{(ν+1)2{−νρμ−ν+(ν+2)ϱμ−ν−(ν+2)σμ−ν}}|,ϑ12=33|134|+33m−2∑μ=1|{133+μ∑ν=1ν(ν+1)2{(ν+2)σμ−ν−ϱμ−ν−(ν−1)ρμ−ν}}|. $
|
(3.46) |
Now we present the analysis of the ternary refinement schemes. A function is called $ C^m $-continuous if its $ m $th order derivative is continuous. The common class of continuous function is $ C = C^0 $. It is natural to think of a $ C^m $ function as being a little bit rough, but the graph of a $ C^3 $ function looks smooth. So we discuss the analysis of the schemes up to $ C^3 $-continuity. The results can be extended similarly. Let {$ \pi^{m}{[0, n]}, \ m = 0, 1, 2, 3\} $ denotes the set of $ C^m $-continuous functions on the closed and bounded interval $ [0, n] $.
Theorem 4.1. If $ f^{0} = \{\left (i/3^0, f^{0}_{i} \right)\} $ is the initial polygon and $ f^{k+1} = \{\left (i/3^{k+1}, f^{k+1}_{i} \right)\} $ is the polygon obtained by TRS at $ (k+1) $th refinement level. If $ \varpi, \ \varpi^* < 1 $ then $ \lim_{k\rightarrow\infty}f^{k} = f \in \pi{[0, n]} = \pi^{0}{[0, n]} $.
Proof. The (3.7), gives
|
$ ‖fk+1−fk‖∞≤ϖ∗maxi‖fki+1−fki‖, $
|
and (3.1), gives
|
$ ‖fk+1−fk‖∞≤ϖ∗(ϖ)kmaxi‖f0i+1−f0i‖, $
|
Since $ \varpi, \ \varpi^* < 1 $ therefore $ \{f^{k}\}_{k = 0}^{\infty} $ is a Cauchy sequence on closed and bounded interval $ [0, n] $. Hence it is convergent. That is
| $ \lim\limits_{k\rightarrow\infty}f^{k} = f \in \pi{[0, n]} = \pi^{0}{[0, n]}. $ |
Hence the proof.
Lemma 4.2. If $ d^{[1] 0} = \left\{\left (i/3^0, d^{[1] 0}_{i} \right)\right\} $ is the initial polygon and $ d^{[1] (k+1)} = $
$ \left\{\left (i/3^{k+1}, d^{[1] (k+1)}_{i} \right)\right\} $ is the polygon obtained by first order DD TRS at $ (k+1) $th refinement level. If $ \varpi^{**}, \ \varpi^{***} < 1 $ and $ c_{1}, c_{2}, c_{3}, c_{4}, c_{5}, c_{6} = 0 $, then $ \lim_{k\rightarrow\infty} d^{[1] k} = d^{[1] } \in \pi{[0, n]} = \pi^{0}{[0, n]} $.
Proof. By (3.23), we have
|
$ ‖d[1](k+1)−d[1]k‖∞≤ϖ∗∗∗maxi‖d[1]ki+1−d[1]ki‖, $
|
Using (3.16), we have
|
$ ‖d[1](k+1)−d[1]k‖∞≤ϖ∗∗∗(ϖ∗∗)kmaxi‖d[1]0i+1−d[1]0i‖, $
|
Since $ \varpi^{**}, \ \varpi^{**} < 1 $, therefore $ \{ d^{[1] k}\}_{k = 0}^{\infty} $ defines a Cauchy sequence on $ [0, n] $ and
| $ \lim\limits_{k\rightarrow\infty} d^{[1] k} = d^{[1]}\in \pi{[0, n]} = \pi^{0}{[0, n]}. $ |
This completes the proof.
Theorem 4.3. Let $ f \in \pi^{0}{[0, n]} $ be the limiting curve produced by the ternary refinement scheme. If $ \varpi^{**}, \ \varpi^{***} < 1 $ and $ c_{1}, c_{2}, c_{3}, c_{4}, c_{5}, c_{6} = 0 $ then $ f\in \pi^{1}{[0, n]} $.
Proof. Lemma 4.2 leads to $ \lim_{k\rightarrow\infty} d^{[1] k} = d^{[1] }\in \pi^{0}{[0, n]} $. Lemma 2.4 gives $ d^{[1] } = f' $. Therefore, we have the result, $ f\in \pi^{1}{[0, n]} $.
Lemma 4.4. If $ d^{[2] 0} = \left\{\left (i/3^0, d^{[2] 0}_{i} \right)\right\} $ is the initial polygon and $ d^{[2] (k+1)} = $
$ \left\{\left (i/3^{k+1}, d^{[2] (k+1)}_{i} \right)\right\} $ is the polygon obtained by second order DD TRS at $ (k+1) $th refinement level. If $ \vartheta, \ \vartheta^{*} < 1 $ and $ \chi_{1}, \chi_{2}, \chi_{3}, \chi_{4}, \chi_{5}, \chi_{6} = 0 $ then $ \lim_{k\rightarrow\infty} d^{[2] k} = d^{[2] } \in \pi^{0}{[0, n]} $.
Proof. By (3.36), we have
|
$ ‖d[2](k+1)−d[2]k‖∞≤ϑ∗maxi‖d[2]ki+1−d[2]ki‖, $
|
Using (3.32), we have
|
$ ‖d[2](k+1)−d[2]k‖∞≤ϑ∗(ϑ)kmaxi‖d[2]0i+1−d[2]0i‖, $
|
Since $ \vartheta, \ \vartheta^{*} < 1 $ therefore $ \{d^{[2] k}\}_{k = 0}^{\infty} $ is a Cauchy convergent sequence. So
| $ \lim\limits_{k\rightarrow\infty} d^{[2] k} = d^{[2]} \in \pi^{0}{[0, n]}. $ |
Hence the proof.
Theorem 4.5. Let $ f \in \pi^{0}{[0, n]} $ be the limiting curve produced by the ternary refinement scheme. If $ \vartheta, \ \vartheta^{*} < 1 $ and $ \varphi_{1}, \varphi_{2}, \varphi_{3}, \varphi_{4}, \varphi_{5}, \varphi_{6} = 0 $ then $ f\in \pi^{2}{[0, n]} $.
Proof. Lemma 4.4 gives $ \lim_{k\rightarrow\infty} d^{[2] k} = d^{[2] }\in \pi^{0}{[0, n]} $. Lemma 2.5 leads to $ d^{[2] } = f'' $. This implies $ f\in \pi^{2}{[0, n]} $.
Lemma 4.6. If $ d^{[3] 0} = \left\{\left (i/3^0, d^{[3] 0}_{i} \right)\right\} $ is the initial polygon and $ d^{[3] (k+1)} = $
$ \left\{\left (i/3^{k+1}, d^{[3] (k+1)}_{i} \right)\right\} $ is the polygon obtained by third order DD TRS at $ (k+1) $th refinement level. If $ \vartheta^{**}, \ \vartheta^{***} < 1 $ and $ \varphi_{7}, \varphi_{8}, \varphi_{9}, \varphi_{10}, \varphi_{11}, \varphi_{12} = 0 $ then $ \lim_{k\rightarrow\infty} d^{[3] k)} = d^{[3] } \in \pi^{0}{[0, n]} $.
Proof. By (3.44), we have
|
$ ‖d[3](k+1)−d[3]k‖∞≤ϑ∗∗∗maxi‖d[3]ki+1−d[3]ki‖, $
|
Using (3.40), we have
|
$ ‖d[3](k+1)−d[3]k‖∞≤ϑ∗∗∗(ϑ∗∗)kmaxi‖d[3]0i+1−d[3]0i‖, $
|
Since $ \vartheta^{**}, \ \vartheta^{***} < 1 $ therefore $ \{ d^{[3] k}\}_{k = 0}^{\infty} $ is a Cauchy convergent sequence. Thus
| $ \lim\limits_{k\rightarrow\infty} d^{[3] k} = d^{[3] }\in \pi^{0}{[0, n]}. $ |
Hence the proof.
Theorem 4.7. Let $ f \in \pi^{0}{[0, n]} $ be the limiting curve produced by the ternary refinement scheme. If $ \vartheta, \ \vartheta^{*} < 1 $ and $ \varphi_{7}, \varphi_{8}, \varphi_{9}, \varphi_{10}, \varphi_{11}, \varphi_{12} = 0 $ then $ f\in \pi^{3}{[0, n]} $.
Proof. Lemma 4.6, implies that $ \lim_{k\rightarrow\infty} d^{[3] k)} = d^{[3] } \in \pi^{0}{[0, n]} $ while Lemma 2.6 leads to $ d^{[3] } = f''' $. This implies $ f\in \pi^{3}{[0, n]} $.
Application and authenticity of the results
We discuss the analysis of the ternary refinement schemes introduced by [8,9,10,16,17]. We conclude that the results obtained by our methods are always equivalent to the one returned by the Laurent polynomial method. We add the Figure 2 for the interest of general readers by the direction of anonymous reviewer of this paper. The Figure 2(d) depicts the smoothness of the limiting curve produced by the ternary scheme. The Figure 2(a), (b) and (c) represent the initial, first and second refinement level of the ternary scheme.
Example 4.1. If the curve is produced by the following 4-point ternary refinement scheme [17]
|
$ {fk+13i=ρ0fki−1+ρ1fki+ρ2fki+1+ρ3fki+2,fk+13i+1=ϱ0fki−1+ϱ1fki+ϱ2fki+2+ϱ3fki+3,fk+13i+2=σ0fki−1+σ1fki+σ2fki+2+σ3fki+3, $
|
where
|
$ {ρ0=(581+53μ), ρ1=(1927−3μ), ρ2=(1354+μ), ρ3=(−1162+13μ),ϱ0=μ, ϱ1=(12−μ), ϱ2=(12−μ), ϱ3=μ,σ0=(−1162+13μ), σ1=(1354+μ), σ2=(1927−3μ), σ3=(581+53μ), $
|
then by Laurent polynomial method the scheme produces $ C^{3} $-continuous curve for $ \mu\in(-\frac{1}{27}, \frac{2}{27}) $. By Theorems 4.1, 4.3, 4.5 and 4.7, we also get the same results.
Example 4.2. If the curve is produced by the following 4-point ternary refinement scheme [9]
|
$ {fk+13i=ρ1fki,fk+13i+1=ϱ0fki−1+ϱ1fki+ϱ2fki+2+ϱ3fki+3,fk+13i+2=σ0fki−1+σ1fki+σ2fki+2+σ3fki+3, $
|
where
|
$ {ρ0=0,ρ1=1,ρ2=0,ρ3=0,ϱ0=−118−16μ, ϱ1=1318+12μ, ϱ2=718−12μ, ϱ3=−118+16μ,σ0=−118+16μ,σ1=718−12μ, σ2=1318+12μ, σ3=−118−16μ, $
|
then by Laurent polynomial method the scheme produces $ C^{2} $-continuous curve over the interval $ \mu\in(\frac{1}{15}, \frac{1}{9}) $. By Theorems 4.1, 4.3, and 4.5, we also get the same results.
Example 4.3. If the curve is produced by the following 3-point ternary refinement scheme [8]
|
$ {fk+13i=ρ0fki−1+ρ1fki+ρ2fki+1,fk+13i+1=ϱ1fki,fk+13i+2=σ0fki−1+σ1fki+σ2fki+1, $
|
where
|
$ {ρ0=(ρ+13), ρ1=(23−2ρ),ρ2=ρ,ϱ0=0,ϱ1=1, ϱ2=0,σ0=ρ, σ1=(23−2ρ),σ2=(ρ+13), $
|
then by both methods the scheme produces $ C^{1} $-continuous curve for $ w\in\left(-\frac{1}{9}, 0\right) $.
Example 4.4. If the curve is produced by the following 6-point ternary refinement scheme [10]
|
$ {fk+13i=ρ2fki,fk+13i+1=ϱ0fki−2+ϱ1fki−1+ϱ2fki+ϱ3fki+1+ϱ4fki+2+ϱ5fki+3,fk+13i+2=σ0fki−2+σ1fki−1+σ2fki+σ3fki+1+σ4fki+2+σ5fki+3, $
|
(4.1) |
where
|
$ {ρ0=0,ρ1=0,ρ2=1,ρ3=0,ρ4=0,ρ5=0,ϱ0=(−1181+13ω), ϱ1=(1327−51ω),ϱ2=(−227+74ω),ϱ3=(7481−46ω),ϱ4=(−527+9ω), ϱ5=ω,σ0=ω, σ1=(−527+9ω), σ2=(7481−46ω),σ3=(−227+74ω),σ4=(1327−51ω), σ5=(−1181+13ω), $
|
then by both methods the scheme produces $ C^{2} $-continuous curve over the interval $ w\in\left(\frac{14}{1215}, \frac{23}{1944}\right) $.
Example 4.5. If the curve is produced by the following 3-point ternary refinement scheme [16]
|
$ {fk+13i=ρ0fki−1+ρ1fki+ρ2fki+1,fk+13i+1=ϱ0fki−1+ϱ1fki+ϱ2fki+2,fk+13i+2=σ0fki−1+σ1fki+σ2fki+2, $
|
(4.2) |
where
|
$ {ρ0=(2572+μ),ρ1=(2336−2μ),ρ2=(172+μ),ϱ0=(18+μ), ϱ1=(34−2μ), ϱ2=(18+μ),σ0=(172+μ),σ1=(2336−2μ), σ2=(2572+μ), $
|
then by both methods the scheme produces $ C^{2} $-continuous curve for $ \mu\in\left(-\frac{1}{72}, \frac{7}{72}\right) $.
Here we present the brief summary of the work done so for in this paper.
● If $ \max\left\{\varpi_1, \varpi_2, \varpi_3\right\} < 1 $ where $ \varpi_1, \varpi_2, \varpi_3 $ are defined in (3.3) then TRS will generate $ C^0 $ continuous curve.
● If $ c_{1} $, $ c_{2} $, $ c_{3} $, $ c_{4} $, $ c_{5} $, $ c_{6} $ defined in (3.15) and (3.22) are equal to zero and $ \max\left\{\varpi^{*}_1, \varpi^{*}_2, \varpi^{*}_3\right\} < 1 $, where $ \varpi^{*}_1, \varpi^{*}_2, \varpi^{*}_3 $ are defined in (3.18) then TRS will generate $ C^1 $ continuous curve.
● If $ \chi_{1} $, $ \chi_{2} $, $ \chi_{3} $, $ \chi_{4} $, $ \chi_{5} $, $ \chi_{6} $ defined in (3.31) and (3.35) are equal to zero and $ \max\{\vartheta_1, \vartheta_2, \vartheta_3\} < 1 $, where $ \vartheta_1, \vartheta_2, \vartheta_3 $ are defined in (3.34) then TRS will generate $ C^2 $ continuous curve.
● If $ \chi_{7} $, $ \chi_{8} $, $ \chi_{9} $ $ \chi_{10} $, $ \chi_{11} $, $ \chi_{12} $ defined in (3.39) and (3.43) are equal to zero and $ \max\{\vartheta_7, \vartheta_8, \vartheta_9\} < 1 $, where $ \vartheta_7, \vartheta_8, \vartheta_9 $ are defined in (3.42) then TRS will generate $ C^3 $ continuous curve.
There are two major techniques to analyze the refinement schemes. These are called Laurent polynomial and divided difference (DD) techniques.
● Our technique is the generalization of the DD technique for ternary refinement schemes.
● We have presented the explicit form of the general inequalities for the analysis of the ternary refinement schemes. These inequalities contain simple algebraic expressions. In these inequalities the polynomial factorization, division and summation are not involved. Simple arithmetic operations such as subtraction and multiplication are involved to evaluate the inequalities.
● While in Laurent polynomial technique, the polynomial factorization, division and summation are involved to evaluate the inequalities. In this technique, the explicit form of the general inequalities are also not available.
● So it is obvious that the computational complexity of our techniques is less than the complexity of Laurent polynomial technique.
In this paper, we have introduced an alternative technique to analyze a class of ternary refinement schemes. A comparative study of the proposed technique with other existing technique has been presented to prove the effectiveness of the proposed technique. It has been observed that the alternative technique has less computational cost comparative to the existing Laurent polynomial technique.
The second author is grate full to HEC Pakistan for awarding the fellowship under the Indigenous Ph.D. Scholarship Scheme. The author Yu-Ming Chu is supported by National Natural Science Foundation of China (Grant Nos. 61673169, 11971142).
Conceptualization, Ghulam Mustafa and Dumitru Baleanu; Formal analysis, Dumitru Baleanu and Yu-Ming Chu; Methodology, Ghulam Mustafa and Syeda Tehmina Ejaz; Supervision, Ghulam Mustafa; Writing original draft, Syeda Tehmina Ejaz and Ghulam Mustafa; Writing, review and editing, Syeda Tehmina Ejaz and Yu-Ming Chu.
The authors declare no conflict of interest.
| [1] |
M. Bächlin, M. Plotnik, D. Roggen, I. Maidan, J. M. Hausdorff, N. Giladi and G. Tröster, Wearable assistant for parkinson's disease patients with the freezing of gait symptom, IEEE Transactions on Information Technology in Biomedicine, 14 (2010), 436-446. doi: 10.1109/TITB.2009.2036165
|
| [2] | K. Bao and S. Intille, "Activity Recognition from User-Annotated Acceleration Data," Proc 2nd Int Conf Pervasive Computing, (2004), 1-17. |
| [3] |
N. Bellomo and C. Dogbé, On the modelling crowd dynamics from scaling to hyperbolic macroscopic models, Mathematical Models and Methods in Applied Sciences, 18 (2008), 1317–-1345. doi: 10.1142/S0218202508003054
|
| [4] |
M. Benocci, C. Tacconi, E. Farella, L. Benini, L. Chiari and L. Vanzago, Accelerometer-based fall detection using optimized zigbee data streaming, Microelectronics Journal, 41 (2010), 703-710. doi: 10.1016/j.mejo.2010.06.014
|
| [5] |
C. Bettini, O. Brdiczka, K. Henricksen, J. Indulska, D. Nicklas, A. Ranganathan and D. Riboni, A survey of context modelling and reasoning techniques, Pervasive and Mobile Computing, 6 (2010), 161-180. doi: 10.1016/j.pmcj.2009.06.002
|
| [6] | I. Borg and P Groenen, "Modern Multidimensional Scaling: Theory and Applications," Springer Series in Statistics, Springer-Verlag, New York, 1997. |
| [7] | M. Buchanan, The science of subtle signals, Strategy+Business, 48 (2007), 68-77. |
| [8] | I. Cohen and M. Goldszmidt, Properties and benefits of calibrated classifiers, Proc. Knowledge Discovery in Databases, 2004, 125-136. |
| [9] |
V. Coscia and C. Canavesio, First-order macroscopic modelling of human crowd dynamics, Math. Mod. Meth. Appl. Sci., 18 (2008), 1217-1247. doi: 10.1142/S0218202508003017
|
| [10] |
N. Davies, D. P. Siewiorek and R. Sukthankar, Special issue: Activity-based computing, IEEE Pervasive Computing, 7 (2008), 20-21. doi: 10.1109/MPRV.2008.26
|
| [11] | R. O. Duda, P. E. Hart and D. G. Stork, "Pattern Classification," Second edition, Wiley-Interscience, New York, 2001. |
| [12] | P. Eades, A heuristic for graph drawing, Congressus Numerantium, 42 (1984), 149-160. |
| [13] |
N. Eagle, A. Pentland and D. Lazer, Inferring friendship network structure by using mobile phone data, Proc Natl Acad Sci U S A, 106 (2009), 15274-15278. doi: 10.1073/pnas.0900282106
|
| [14] | T. Fawcett, "ROC graphs: Notes and practical considerations for researchers," Tech. report, HP Laboratories, 2004. |
| [15] | D. Figo, P. Diniz, D. Ferreira and J. Cardoso, Preprocessing techniques for context recognition from accelerometer data, Pervasive and Mobile Computing, 14 (2010), 645-662. |
| [16] |
T. M. J Fruchterman and E. M. Reingold, Graph drawing by force-directed placement, Software - Practice and Experience, 21 (1991), 1129-1164. doi: 10.1002/spe.4380211102
|
| [17] |
M. González and A.-L. Barabási, Complex networks: From data to models, Nature Physics, 3 (2007), 224-225. doi: 10.1038/nphys581
|
| [18] |
D. Helbing, L. Buzna, A. Johansson and T. Werner, Self-organized pedestrian crowd dynamics: Experiments, simulations, and design solutions, Transportation Science, 39 (2005), 1-24. doi: 10.1287/trsc.1040.0108
|
| [19] |
D. Helbing, I. Farkas and T. Vicsek, Simulating dynamical features of escape panic, Nature, 407 (2000), 487-–490. doi: 10.1038/35035023
|
| [20] | D. Helbing and A. Johansson, "Pedestrian, Crowd and Evacuation Dynamics," Meyers Encyclopedia of Complexity and Systems Science, Springer, Berlin, 2009. |
| [21] |
D. Helbing and P. Molnár, Social force model for pedestrian dynamics, Physical Review E, 51 (1995), 4282-4286. doi: 10.1103/PhysRevE.51.4282
|
| [22] |
S. Hoogendoorn and P. Bovy, Simulation of pedestrian flows by optimal control and differential games, Opt. Cont. Appl. Meth., 24 (2003), 153-172. doi: 10.1002/oca.727
|
| [23] |
A. Johansson, D. Helbing and H. Z. Al-Abideen, From crowd dynamics to crowd safety: A video-based analysis, Advances in Complex Systems, 11 (2008), 497-527. doi: 10.1142/S0219525908001854
|
| [24] |
A. Johansson, D. Helbing and P. S. Shukla, Specification of the social force pedestrian model by evolutionary adjustment to video tracking data, Advances in Complex Systems, 10 (2007), 271-288. doi: 10.1142/S0219525907001355
|
| [25] | S. Kallio, J. Kela, P. Korpipää and J. Mäntyjärvi, User independent gesture interaction for small handheld devices, International Journal of Pattern Recognition and Artificial Intelligence, 20 (2006), 505-524. |
| [26] |
A. Kesting, M. Treiber and D. Helbing, Connectivity statistics of store-and-forward intervehicle communication, IEEE Transactions on Intelligent Transportation Systems, 11 (2010), 172-181. doi: 10.1109/TITS.2009.2037924
|
| [27] |
J. Kleinberg, The convergence of social and technological networks, Communications of the ACM, 51 (2008), 66-72. doi: 10.1145/1400214.1400232
|
| [28] | M. H. Ko, G. West, S. Venkatesh and M. Kumar, "Online Context Recognition in Multisensor Systems Using Dynamic Time Warping," Proc. Conf. Intelligent Sensors, Sensor Networks and Information Processing Conference, (2005), 283-288. |
| [29] | N. D. Lane, E. Miluzzo, H. Lu, D. Peebles, T. Choudhury and A. T. Campbell, A survey of mobile phone sensing, IEEE Communications Magazine, 48 (2010), 140-150. |
| [30] |
D. Lazer, A. Pentland, L. Adamic, S. Aral, A.-L. Barabási, D. Brewer, N. Christakis, N. Contractor, J. Fowler, M. Gutmann, T. Jebara, G. King, M. Macy, D. Roy and M. Van Alstyne, Computational social science, Science, 323 (2009), 721-723. doi: 10.1126/science.1167742
|
| [31] |
S. Mann, Humanistic computing: "Wearcom" as a new framework and application for intelligent signal processing, Proceedings of the IEEE 86 (1998), 2123-2151. doi: 10.1109/5.726784
|
| [32] | S. McKeever, J. Ye, L. Coyle and S. Dobson, "Using Dempster-Shafer Theory of Evidence for Situation Inference," Proceedings of the 4th European conference on Smart sensing and context, Berlin, Heidelberg, EuroSSC'09, Springer-Verlag, (2009), 149-162. |
| [33] |
T. M. Mitchell, Mining our reality, Science, 326 (2009), 1644-1645. doi: 10.1126/science.1174459
|
| [34] |
M. Moussaïd, N. Perozo, S. Garnier, D. Helbing and G. Theraulaz, The walking behaviour of pedestrian social groups and its impact on crowd dynamics, PLoS One, 5 (2010), e10047. doi: 10.1371/journal.pone.0010047
|
| [35] | J.-K. Onnela, J. Saramäki, J. Hyvönen, G. Szabó, M. A. de Menezes, K. Kaski, A.-L. Barabási and J. Kertész, Analysis of a large-scale weighted network of one-to-one human communication, New Journal of Physics, 9 (2007). |
| [36] |
J. A. Paradiso, J. Gips, M. Laibowitz, S. Sadi, D. Merrill, R. Aylward, P. Maes and A. Pentland, Identifying and facilitating social interaction with a wearable wireless sensor network, Personal and Ubiquitous Computing, 4 (2010), 137-152. doi: 10.1007/s00779-009-0239-2
|
| [37] | A. Pentland, "Honest Signals: How They Shape Our World," Bradford Books, 2008. |
| [38] |
A. Pentland, T. Choudhury, N. Eagle and P. Singh, Human dynamics: Computation for organizations, Pattern Recognition Letters, 26 (2005), 503-511. doi: 10.1016/j.patrec.2004.08.012
|
| [39] |
H. Qian, Y. Mao, W. Xiang and Z. Wang, Recognition of human activities using SVM multi-class classifier, Pattern Recognition Letters, 31 (2010), 100-111. doi: 10.1016/j.patrec.2009.09.019
|
| [40] | C. Randell and H. Muller, "Context Awareness by Analysing Accelerometer Data," ISWC 2000: Proc. of the 4th Int'l Symposium on Wearable Computers, October 2000, 175-176. |
| [41] |
A. Ranganathan, J. Al-Muhtadi and R. H. Campbell, Reasoning about uncertain contexts in pervasive computing environments, Pervasive Computing, IEEE, 3 (2004), 62-70. doi: 10.1109/MPRV.2004.1316821
|
| [42] | S. Saxena, F. Brémond, M. Thonnat and R. Ma, "Crowd Behavior Recognition for Video Surveillance," Advanced Concepts for Intelligent Vision Systems (Berlin), Lecture Notes in Computer Science, 5259, Springer, (2008), 970-981. |
| [43] | S. E. Schaeffer, Graph clustering, Computer Science Review, 1 (2007), 27-64. |
| [44] | S. H. Shin, M. S. Lee, C. G. Park and H. S. Hong, "Pedestrian Dead Reckoning System with Phone Location Awareness Algorithm," Proc. Position Location and Navigation Symposium (PLANS), IEEE Press, 2010, 97-101. |
| [45] | T. Starner, J. Weaver and A. Pentland, Real-time American sign language recognition using desk and wearable computer based video, IEEE Transactions on Pattern Analysis and Machine Intelligence, 20 (1998), 1371-1375. |
| [46] |
T. Stiefmeier, D. Roggen, G. Ogris, P. Lukowicz and G. Tröster, Wearable activity tracking in car manufacturing, IEEE Pervasive Computing, 7 (2008), 42-50. doi: 10.1109/MPRV.2008.40
|
| [47] | J. A. Ward, P. Lukowicz, G. Tröster and T. Starner, Activity recognition of assembly tasks using body-worn microphones and accelerometers, IEEE Trans. Pattern Analysis and Machine Intelligence, 28 (2006), 1553-1567. |
| [48] | J. A. Ward, P. Lukowicz and H. Gellersen, Performance metrics for activity recognition, ACM Transactions on Information Systems and Technology, 2 (2011), 6:1-6:23. |
| [49] | M. Wirz, D. Roggen and G. Tröster, "Decentralized Detection of Group Formations from Wearable Acceleration Sensors," IEEE Int. Conf. on Computational Science and Engineering, IEEE Press, 2009, 952-959. |
| [50] | _____, "A Methodology Towards the Detection of Collective Behavior Patterns by Means of Body-Worn Sensors," UbiLarge workshop at the 8th Int. Conf. on Pervasive Computing, 2010. |
| [51] | _____, "User Acceptance Study of a Mobile System for Assistance During Emergency Situations at Large-Scale Events," 3rd International Conference on Human Centric Computing, 2010. |
| [52] | P. Zappi, C. Lombriser, E. Farella, D. Roggen, L. Benini and G. Tröster, "Activity Recognition from On-Body Sensors: Accuracy-Power Trade-Off by Dynamic Sensor Selection," 5th European Conf. on Wireless Sensor Networks (ed. R. Verdone), Springer, (2008), 17-33. |
| [53] |
B. Zhan, D. N. Monekosso, P. Remagnino, S. A. Velastin and L.-Q. Xu, Crowd analysis: A survey, Machine Vision and Applications, 19 (2008), 345-–357. doi: 10.1007/s00138-008-0132-4
|
| 1. | Humaira Mustanira Tariq, Rabia Hameed, Ghulam Mustafa, A Study on the Class of Non-Symmetric 3-Point Relaxed Quaternary Subdivision Schemes, 2022, 10, 2169-3536, 132164, 10.1109/ACCESS.2022.3230281 |
Daniel Roggen, Martin Wirz, Gerhard Tröster, Dirk Helbing. Recognition of crowd behavior from mobile sensors with pattern analysis and graph clustering methods[J]. Networks and Heterogeneous Media, 2011, 6(3): 521-544. doi: 10.3934/nhm.2011.6.521
DownLoad:
