Ph.D Thesis

Ph.D StudentItai Uri
SubjectTwo Linearly Asymptotic Subdivision Schemes Refining
Curves and Matrices
DepartmentDepartment of Applied Mathematics
Supervisors PROF. Nira Dyn
PROF. Gershon Elber


Subdivision schemes are attractive methods for generating a smooth object from discrete data by repeated refinements. These linear schemes that refine points and generate a function, a curve or a surface, have many desirable properties such as fast convergence and smoothness of the generated objects. Therefore, subdivision schemes have gained popularity in recent years as an important tool in approximation theory, computer modeling etc.

These schemes preform very well for dense samples.  However, for sparse samples we get poor results.  Hence there is a need for schemes that mimic that linear case for dense samples and give good performance for sparse samplings. Schemes that provide these properties are called asymptotically linear Subdivision Schemes.  Schemes of this type consist of schemes for Lie groups, Riemann manifolds etc.

This dissertation introduces two generalizations of linear point-refining schemes to schemes for geometric objects which are of this kind. The first one constructs a surface by refining a sequence of non-intersecting curves. The second extension generates a matrix valued function from a sequence of symmetric positive definite matrices.

The curve refinement schemes are an extension of the corner cutting schemes by replacing points by curves. This was achieved by using a correspondence between consecutive curves.  The above was done in two attempts. The first one is independent of any parameterization of the curves. For this scheme we prove convergence to a limit set that retains geometrical properties of the initial curves, and under certain geometric condition on the initial curves and correspondence. The second is based on the arc length parameterization of the curves. By taking this into account we proved that the limit set is a smooth surface that retains all the properties we proved in the first attempt.

The second generalization in this dissertation is an extension of the interpolatory 4-point subdivision scheme to data consisting of symmetric positive definite matrices. The scheme is based on an explicit formula for the geometric average of symmetric positive definite matrices. It turns out that this average agrees with the geodesic line of a Riemann metric. The scheme converges to a smooth matrix valued function. The limit function retains many important algebraic properties of the interpolated matrices.