Eigenvalue optimization in C Square Subdivision and Boundary Subdivision

Subdivision is a method to construct smooth surfaces from polygonal meshes used in computer graphics and geometric modeling applications. In order to obtain subdivision surfaces that are C 2 smooth we have to use a rather cumbersome scheme. The main difficulty is caused by the so-called extraordinary vertices, which are vertices that do not have 6 neighbors in the triangular case (4 neighbors in the quadrilateral case). The extraordinary vertex with half the number of vertices as the regular vertex turns out to be a special case. We use this fact to create a subdivision scheme that is C2 flexible for this vertex. The scheme's characteristic map is equal to Bers' chart.;For both types of meshes, in the final step of creating the subdivision scheme, we solve an eigenvalue optimization problem. In the triangular case we find the exact global optimum. In the quadrilateral case we solve the optimization problem numerically. In both cases the function that is minimized is the reduced spectral radius of the subdivision matrix depending on parameters, that is the largest modulus of the eigenvalues excluding certain known, fixed, eigenvalues.;We are able to approximate a round sphere very well with a very coarse mesh and explore several other applications of the scheme in the triangular setting.;We furthermore develop theory to handle boundary subdivision. The starting point for our theory is a precise description of the class of surfaces that we would like to be able to model using subdivision. We demonstrate how the standard constructions of subdivision theory generalize to the case of surfaces with piecewise-smooth boundary and extend the techniques for analysis of C1-continuity. Since the extraordinary vertex is a boundary point we have to change some aspects of the theory. We analyze several specific boundary subdivision rules for Loop and Catmull-Clark subdivision schemes.;Finally, we give an analysis of the subdifferential of the spectral abscissa (maximum of the real part of the eigenvalue), a nonsmooth, nonconvex function, for a matrix with a specific Jordan structure.