Analysis of non-uniform subdivision schemes

The theory of subdivision schemes has had an impact on several applied areas of mathematics and engineering and, in return, has been greatly influenced by applications. Subdivision offers mathematical tools for computer animation, signal and image processing, progressive geometric data transmission, and it is a mathematical theory of efficient algorithmic generation of curves and surfaces. The underlying algorithms are recursive and generate denser and denser sets of points, usually on a plane or in the three dimensional space. These sets of points form vertices of polygonal lines or meshes that ideally converge to curves or surface with desired properties dictated by applications. The most important properties of such curves or surfaces are their smoothness and shape. In the case of equally spaced and/or level independent data, these properties are well understood and are characterized using the joint spectral radius techniques (a matrix based approach). It is still an open problem, whether the characterization of the convergence and smoothness of general non-uniform subdivision schemes (which handle irregularly spaced and level dependent data) is possible via the joint spectral radius approach. This project will either give an affirmative answer to this open problem, thus, demonstrating the full strength of the joint spectral radius approach, or expose its limitations. Successful completion of this project will simplify the analysis of non-uniform subdivision schemes by providing a general, computationally efficient method for checking their convergence and determining their smoothness. It will also make the construction of new application driven schemes more coherent.

Subdivision schemes are recursive algorithms for generation of curves and surfaces. Subdivision is used in computer animation, progressive compression of 3-d meshes or interactive surface viewing. The project ``Analysis of non-uniform subdivision schemes" studied the fundamental properties of subdivision - convergence, smoothness and geometric properties of underlying curves and surfaces. We characterized the Hölder regularity of anisotropic multivariate subdivision schemes in terms of the joint spectral radii of finite matrix sets restricted to certain isotropic invariant subspaces. This result resolves a 25-year old problem. The matrix sets used for the computation of the joint spectral radius have been so far constructed by hand. We developed a first algorithmic approach for construction of such matrix sets. Combined with our modified invariant polytope algorithm it provides a user friendly and fully automated computational tool for determining the smoothness of various subdivision limits. This software is of independent interest for several areas of mathematics that make use of the joint spectral radius techniques: code theory, linear switched systems, etc. Apart from smoothness, the variety of shapes generated by subdivision is of practical importance. We fully characterized the class of analytic functions generated by level dependent subdivision with masks of bounded and unbounded support as well as by vector subdivision.