DK3: Geometric Solvers for Polynomial Systems/Theory and Algorithms for Truncated Hierarchical B-splines

Robust algorithms for solving systems of polynomial equations, which are based on Bézier clipping and its variants, find all roots in a bounded domain and have second order convergence for single roots.  E.g., such techniques are needed for solving intersection problems in Computer Aided Design, but they can also be useful for applications in robotics and numerical simulation.

We formulated a new geometric algorithm for solving univariate polynomials via approximation by quadratic enclosures with good convergence rates: 3 for single and 3/2 for double roots. In particular, it performs very well in the case of two roots which are relatively close to each other. We explored several extensions and related applications.

During the second period the focus of the work shifted to the Truncated Hierarchical B-splines.

Tensor–product B–spline and their non–uniform rational extension (NURBS) are currently used as standard modeling tool in Computer Aided Design (CAD) software libraries and for numerical simulation in Isogeometric Analysis. However, in many applications e.g., in industrial processes requiring high precision, this mathematical model does not provide sufficient flexibility as an effective geometric modeling option. In particular, the multivariate tensor-product construction precludes the design of adaptive spline representations that support localized mesh refinement without propagation of the refinement outside the region of interest. Truncated hierarchical B-splines (THB-splines) provide the possibility of introducing different levels of resolution in an adaptive framework, thus enabling localized refinement, while simultaneously preserving the main properties of standard B-splines, for instance the partition of unity and linear independence. The main goal of the project was to introduce an efficient representation of the hierarchical domain structure together with optimal evaluation algorithms. More precisely, the student investigated suitable algorithms and data structures, addressing both theoretical (complexity) and practical (implementation) aspects. The successful completion of these tasks naturally led to exploration of the improved modeling possibilities of THB–splines with a comparison to the standard B–spline model.

Supervisor: Prof. Bert Jüttler