Subdivision, interpolation and splines

Thesis (MSc)--University of Stellenbosch, 2000.ENGLISH ABSTRACT: In this thesis we study the underlying mathematical principles of stationary subdivision, which can be regarded as an iterative recursion scheme for the generation of smooth curves and surfaces in computer graphics. An important tool for our work is Fourier analysis, from which we state some standard results, and give the proof of one non-standard result. Next, since cardinal spline functions have strong links with subdivision, we devote a chapter to this subject, proving also that the cardinal B-splines are refinable, and that the corresponding Euler-Frobenius polynomial has a certain zero structure which has important implications in our eventual applications. The concepts of a stationary subdivision scheme and its convergence are then introduced, with as motivating example the de Rahm-Chaikin algorithm. Standard results on convergence and regularity for the case of positive masks are quoted and graphically illustrated. Next, we introduce the concept of interpolatory stationary subdivision, in which case the limit curve contains all the original control points. We prove a certain set of sufficient conditions on the mask for convergence, at the same time also proving the existence and other salient properties of the associated refinable function. Next, we show how the analysis of a certain Bezout identity leads to the characterisation of a class of symmetric masks which satisfy the abovementioned sufficient conditions. Finally, we show that specific special cases of the Bezout identity yield convergent interpolatory symmetric subdivision schemes which are identical to choosing the corresponding mask coefficients equal to certain point evaluations of, respectively, a fundamental Lagrange interpolation polynomial and a fundamental cardinal spline interpolant. The latter procedure, which is known as the Deslauriers-Dubuc subdivision scheme in the case of a polynomial interpolant, has received attention in recent work, and our approach provides a convergence result for such schemes in a more general framework. Throughout the thesis, numerical illustrations of our results are provided by means of graphs.AFRIKAANSE OPSOMMING: In hierdie tesis ondersoek ons die onderliggende wiskundige beginsels van stasionêre onderverdeling, wat beskou kan word as 'n iteratiewe rekursiewe skema vir die generering van gladde krommes en oppervlakke in rekenaargrafika. 'n Belangrike stuk gereedskap vir ons werk is Fourieranalise, waaruit ons sekere standaardresuJtate formuleer, en die bewys gee van een nie-standaard resultaat. Daarna, aangesien kardinale latfunksies sterk bande het met onderverdeling, wy ons 'n hoofstuk aan hierdie onderwerp, waarin ons ook bewys dat die kardinale B-Iatfunksies verfynbaar is, en dat die ooreenkomstige Euler-Frobenius polinoom 'n sekere nulpuntstruktuur het wat belangrike implikasies het in ons uiteindelike toepassings. Die konsepte van 'n stasionêre onderverdelingskema en die konvergensie daarvan word dan bekendgestel, met as motiverende voorbeeld die de Rahm-Chaikin algoritme. Standaardresultate oor konvergensie en regulariteit vir die geval van positiewe maskers word aangehaal en grafies geïllustreer. Vervolgens stelons die konsep van interpolerende stasionêre onderverdeling bekend, in welke geval die limietkromme al die oorspronklike kontrolepunte bevat. Ons bewys 'n sekere versameling van voldoende voorwaardes op die masker vir konvergensie, en bewys terselfdertyd die bestaan en ander toepaslike eienskappe van die ge-assosieerde verfynbare funksie. Daarna wys ons hoedat die analise van 'n sekere Bezout identiteit lei tot die karakterisering van 'n klas simmetriese maskers wat die bovermelde voldoende voorwaardes bevredig. Laastens wys ons dat spesifieke spesiale gevalle van die Bezout identiteit konvergente interpolerende simmetriese onderverdelingskemas lewer wat identies is daaraan om die ooreenkomstige maskerkoëffisientegelyk aan sekere puntevaluasies van, onderskeidelik, 'n fundamentele Lagrange interpolasiepolinoom en 'n kardinale latfunksie-interpolant te kies. Laasgenoemde prosedure, wat bekend staan as die Deslauriers-Dubuc onderverdelingskema in die geval van 'n polinoominterpolant, het aandag ontvang in onlangse werk, en ons benadering verskaf 'n konvergensieresultaat vir sulke skemas in 'n meer algemene raamwerk. Deurgaans in die tesis word numeriese illustrasies van ons resultate met behulp van grafieke verskaf