American Journal of Computational Mathematics, 2013, 3, 217-221 http://dx.doi.org/10.4236/ajcm.2013.33031 Published Online September 2013 (http://www.scirp.org/journal/ajcm) A Family of 4-Point n-Ary Interpolating Scheme Reproducing Conics Mehwish Bari, Ghulam Mustafa Department of Mathematics, The Islamia University of Bahawalpur, Bahawalpur, Pakistan Email: ghulam.mustafa@iub.edu.pk, mehwishbari@yahoo.com Received April 16, 2013; revised June 5, 2013; accepted July 5, 2013 Copyright © 2013 Mehwish Bari, Ghulam Mustafa. This is an open access article distributed under the Creative Commons Attribu- tion License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. ABSTRACT The n-ary subdivision schemes contrast favorably with their binary analogues because they are capable to produce limit functions with the same (or higher) smoothness but smaller support. We present an algorithm to generate the 4-point n-ary non-stationary scheme for trigonometric, hyperbolic and polynomial case with the parameter for describing curves. The performance, analysis and comparison of the 4-point ternary scheme are also presented. Keywords: Interpolation; Non-Stationary; Univariate Ternary Refinement; Continuity; Conic Section 1. Introduction Subdivision is a method for making smooth curves/sur- faces, which first emerged an addition of splines to arbi- trary topological control nets. Effectiveness of subdivi- sion algorithms, their flexibility and ease make them ap- propriate for many relative computer graphics applica- tions. The schemes generating curves are considered to be the basic tools for the design of schemes generating surfaces. A general form of univariate n-ary subdivision scheme S which maps a control polygon kk ii ff to a re- fined polygon 11kk ii ff is defined by 1,0,1,2,, kk ni snj sij j fafS 1,n where the set i aai of coefficients is called mask of the subdivision scheme. The set of coefficients : kk i aai kk a d etermines the subdivision ru le at level and is termed as the mask at -th level. If the mask is independent of , namely if , the subdivision scheme is called stationary otherwise it is called non-stationary. Sometimes, in computer graphics and geometric modeling, it is required to have schemes to construct circular parts or parts of conics. It seems that (linear) stationary schemes cannot generate conics and non-stationary schemes have such a capability to gener- ate trigonometric polynomials, trigonometric splines and, in particular, circles, ellipses and so on. Such schemes k k, k aak are useful in computer graphics and geometric modeling. Successful efforts have been made to establish approxi- mating and interpolating non-stationary schemes which can provide smooth curves and reproduce circle or some trigonometric curves. The theoretical bases regarding non-stationary schemes are derived from the analysis of stationary schemes. Jena et al. [1] worked on 4-point binary non-stationary subdi- vision scheme for curve interpolation. Yoon [2] pre- sented the analysis of binary non-stationary interpolating scheme based on exponential polynomials. Beccari et al. [3] worked on 4-point binary non-stationary uniform ten- sion controlled interpolating scheme reproducing conics. Daniel and Shunmugaraj [4] presented 4-point ternary non-stationary interpolating subdivision scheme. In this paper, we present an algorithm to construct 4-point n-ary scheme. For simplicity, we have discussed and analyzed 4-point ternary scheme. This paper is organized as follows. Section 2 presents the construction of 4-point n-ary non-stationary interpo- lating subdivision schemes. As an example, 4-point ter- nary scheme is presented in this section. Section 3 pro- vides the smoothness of proposed schemes. In the last section conclusion and visual performance of proposed schemes are presented. 2. Construction of 4-Point n-Ary Scheme Here we suggest the following algorithm to construct the non-stationary n-ary 4-point 2,3,4, ,n interpo- C opyright © 2013 SciRes. AJCM
M. BARI, G. MUSTAFA 218 lating schemes for trigonometric, hyperbolic and poly- nomial cases. Choose interpolating function 01 23 cossin , xaaxaxa x 01 23 cosh sinh or , xaaxa xa x or 23 01 23 . xaaxaxax Then define the points k i pi at level k and get system of linear equations by interpolating. The data k ih p corresponding to the abscissas ,1,0,1, k ht xh n 2. Solve the system of linear equations by any well known method to get the values of unknowns. Evaluate the interpolating function x at the grid points 1 1:2,3,,. k rt rn n Define the new points 1. kk ni i pp Define the new points 11 1,1,2,3,, k ni jk rt pf jrr n ,n as a lin- ear combination of four consecutive points 1 k i p , , and k i p 1 k i p2. k i p Ternary 4-Point Interpolating Scheme Given a set of control points at level , using above algorithm, we define a unified ternary 4-point in- terpolating scheme that makes a new set of control points by the rule: k Pk 1k p 1 3 1 3111 23142 1 324 132 112 , , , kk ii kkkkkkkkk iiiii kkkkkkkkk iiii pp ppppp ppppp where 11 24 1, kk k5 3 21 1 41(161) kk kk 5 , 43 3111 4882 1, kk kkk5 41 41 kk k5 , with 2 2 511 641 21, kkk where the parameter 1k can easily be updated at each subdivision step through following equation 10 1,0,1,2,, 1, 2k kk . (2.2) Therefore, given parameter , k the subdivision rules are achieved by first computing 1k using Equation (2. 2) an d th en by substituting 1k into (2.1). As a result, depending on the choice of the parameter, we get differ- ent schemes. For 11 1cos h 3 kk t i 3 ,cost k and 1 in (2.1), we can generate following schemes exact for tri- gonometric (2.3), hyperbolic (2.4) and polynomial (2.5) respectively. 1 3 1 3111231 42 1 324 132 112 , , , kk ii kkkkkkkkk iiiii kkkkkkkkk iiii pp ppppp ppppp (2.3) where i (2.1) 1 12sin33sin 23, kkk tt k 11 22sin2 3sin36sin233sin3, kkkkk tt tt k 11 33sin 23sin 232sin36sin3, kkkkk tttt k 1 4sin 33sin 3, kkk tt k 6sin3cos 31 kkk tt . 1 3 1 3111 231 42 1 324 132 112 , , , kk ii kkkkkkkkk iiiii kkkkkkkkk iiii pp ppppp ppppp kk i (2.4) where 11 , 22 , kk 33 , kk 44 , kk after replacing sin and cos functions by sinh and cosh func- tions in 12 ,, k34 ,. kkk 1 3 1 3111 2 1 3211 2 , 560304 , 81818181 430605 , 81 8181 81 kk ii kkkk iiii kkkk iiii pp ppppp pppp k i k i p (2.5) Remark 2.1. The scheme (2.3) and (2.4) can be consid- ered as a non-stationary counterpart of the DD stationary scheme [5] i.e. scheme (2.5) because, the masks of the schemes (2.3) and (2.4) converge to the mask of scheme (2.5): Copyright © 2013 SciRes. AJCM
M. BARI, G. MUSTAFA 219 1122 33 44 560 ,, 81 8181 4,.s 81 a kkkk kk kk k 30 , 3. Smoothness Analysis The subdivision scheme given in the previous subsection, the coefficients 1,2 ,3,4 k ii in (2.1) may vary from one refinement level to another. Hence the scheme is non- stationary and its smoothness properties can be derived by asymptotical equivalence [6] with the corresponding stationary scheme. Two subdivision schemes and are said asymptotically equivalent if k a S a S . ka ka SS In particular, our analysis is based on the generalization of Theorem 8 in [6] to ternary sub- division. Since our schemes (2.3) and (2.4) are non-stationary then we can use the theory of asymptotic equivalence and generating function formalism [7] to investigate the smoothness of the schemes. First, we need some esti- mates of k i and which are specified in subsequent lemmas. ,1,2,3,4, k ii Lemma 3.1. The mask of scheme (2.3) satisfies following inequali- ties for sufficiently large . k 1) 1 12 , 33 k 2) 2 41, 3 k 3) 3 104 , 27 3 k 4) 4 11 . 63 k Proof. We make use the inequalities sin sin aa bb for 02 ab , csc csctt for 02 t and sin cos x (or 1 csc xcos x ) for 02 x to prove the above inequa lities: Since 11 12 1 22 2sin36sin 3cos3 12sin3sin2 3 sin 3sin 3cos3. 6sin3sin2 32sin3sin2 3 kkk k kk kk kkkk ttt tt tt tt tt k t Then for k 11 12 13cos 313cos 31 63 6sin23 kk k k tt t and also for , we get k 1 12 21 2 2sin36sin3cos3 12sin3sin2 3 22 6sin232. 3 12sin2 3 kk k kk k k ttt tt t t k This proves 1). The pro o fs of 2) , 3) an d 4) are sim i l ar. Lemma 3.2. The coefficients in the scheme (2.4) satisfy following inequalities when subdivision level . k 1) 1 10, 3 k 2) 2 77 , 66 k 3) 3 44 , 33 k 4) 4 10. 6 k Proof. We make use of following inequality of [8] 2 11cos cos,,. cosh2222 xx x x This claim holds true if the function x is non- negative on 0, 2. Some other inequalities for 02 x are 1 2 sinhsinh,sinh 0, 33 kk xx x 11 ,0 coshsinh1 cosh x xx x . Since 1 1 2sinh33sinh 23 6sinh3cosh31 2sinh3. 6sinh3cosh31 kk k kk k kk tt tt t tt Then for k 1 2 1cos 3 1 33cosh313 1cos3 1cos 31, 3 32sin23 k k kk k k t tt t t Copyright © 2013 SciRes. AJCM
M. BARI, G. MUSTAFA 220 and similarly for k 1 1 2sinh33sinh23 6sinh3cosh31 3sinh 30. 6sinh 3cosh 31 kk k kk k kk tt tt t tt This proves 1). The pro o fs of 2) , 3) an d 4) are sim i l ar. The following two Lemmas are the consequence of previous Lemm as. Lemma 3.3. 1) 1559 , 81 81 k 2) 260 21, 81 81 k 3) 330 78, 81 81 k 4) 4431 . 81 81 k Proof. Since 15 81 k as and by 1) of k Lemma 3.1, we have 1). Similarly, we get 2), 3) and 4). Lemma 3.4. 1) 155 , 81 81 k 2) 260 23, 81 54 k 3) 330 78, 81 81 k 4) 444 . 81 81 k Proof. Since 15 81 k as and by 1) of k Lemma 3.2, we have 1). Similarly, we get 2), 3) and 4). Lemma 3.5. The Laurent polynomial kz of the level of the scheme th k k S defined by (2.1) can be written as 2 1 3 kk zz zaz 2 1 where 543 414 1 34 123434 123 1144 33 33 33 33 3. kkkkkkk kkkk kk kkk k azzz zz z zzz Proof. By (2.1), we have 5421 413 22 245 314 1 . k kkkkk kkk zzzzzz zzz It can be easily verified that 2 1. 3 kk zz za z Lemma 3.6. The stationary scheme a S defined by (2.5) associ- ated with the symbol 542 1 245 145306081 60 81 30 5 4 azzzzzz zzz 1 is 1.C Proof. To prove that a S is consider 1,C 2 2 32123 3 1 14 3 617634. 27 az bz zz zzzzzz Since 3313 max ,, 25 99 max, ,1 27 27 27 bjj jj j Sbb 2j b then by [[7], corollary 4.11] the scheme a S is 1.C Lemma 3.7. The scheme k S defined by (2.1) is 1.C Proof. Since a S is by Lemma 3.6, in view of [[6], Theorem 8(a)], it is sufficient to show that 1 C 03k ka k SS where 333131 3232 1434 14 1234 max ,, 54 26 max 3333, 27 2727 12 2333333 . 27 27 ka kk k jjj jjj jj j kkkk kk kkkk SS aa a 9 Note that 1234 1234 29 333327 56030. 81818181 kkkk kkkk 4 Since 1 0 5 3, 81 kk k Copyright © 2013 SciRes. AJCM
M. BARI, G. MUSTAFA Copyright © 2013 SciRes. AJCM 221 5. Acknowledgements 2 0 60 3, 81 kk k 3 0 30 381 kk k and This work is supported by the Indigenous Ph.D Schol- arship Scheme of Higher Education Commission (HEC) Pakistan. 1 0 4 3 81 kk k , then by Lemma 3.3, it follows that REFERENCES 11234 0 29 3 81 kkkkk k . [1] M. K. Jena, P. Shunmugaraj and P. C. Das, “A Non-Sta- tionary Subdivision Scheme for Curve Interpolation,” ANZIAM Journal, Vol. 44, No. E, 2003, pp. 216-235. By Lemma 3.3, we can also show that 1 0 5 33 , 27 kk k 4 0 4 33 , 27 kk k [2] J. Yoon, “Analysis of Non-Stationary Interpolatory Sub- division Schemes Based on Exponential Polynomials,” Geometric Modeling and Processing, Vol. 4077, 2006, pp. 563-570. 34 0 26 33 327 kk k k and [3] C. Beccari, G. Casciola and L. Romani, “A Non-Station- ary Uniform Tension Controlled Interpolating 4-Point Scheme Reproducing Conics,” Computer Aided Geomet- ric Design, Vol. 24, No. 1, 2007, pp. 1-9. doi:10.1016/j.cagd.2006.10.003 14 0 2 36 6. 27 kkk k Hence 03k ka kSS . [4] S. Daniel and P. Shunmugaraj, “Some Interpolating Non- Stationary Subdivision Schemes,” International Sympo- sium on Computer Science and Society, Kota Kinabalu, 16-17 July 2011, pp. 400-403. doi:10.1109/ISCCS.2011.110 4. Conclusions To the aim of reproducing conic sections, we introduce an algorithm for generation of 4-point n-ary interpolating scheme. In particular, we define 4-point interpolating scheme that unifies three different curves schemes which are capable of representing trigonometric, hyperbolic and polynomial functions. [5] G. Deslauriers and S. Dubuc, “Symmetric Iterative Inter- polation Processes,” Constructive Approximation, Vol. 5, No. 1, 1989, pp. 49-68. doi:10.1007/BF01889598 [6] N. Dyn and D. Levin, “Analysis of Asymptotically Equi- valent Binary Subdivision Schemes,” Journal of Mathe- matical Analysis and Applications, Vol. 193, No. 2, 1995, pp. 594-621. doi:10.1006/jmaa.1995.1256 The resulting ternary algorithm allows u s to efficiently define limit curves that combine all the ingredients of locality, smoothness, user-independence, local ten- sion control and reproduction of conics, see Figure 1. 1 C[7] N. Dyn and D. Levin, “Subdivision Schemes in Geomet- ric Modelling,” Acta Numerica, Vol. 11, 2002, pp. 73-144. doi:10.1017/S0962492902000028 [8] R. Klen, M. Lehtonen and M. Vuorinen, “On Jordan Type Inequalities for Hyperbolic Functions,” Journal of Ine- qualities and Applications, Vol. 2010, 2010, Article ID: 362548. (a) (b) (c) (d) Figure 1. Dotted lines indicate the initial closed and open polygons. Solid continuous curves are generated by pro- posed ternary interpolating scheme for trigonometric case.
|