Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, April 30, 2007

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
MA 041

Lecture - 14:15

Jack Snoeyink - Computer Science, UNC Chapel Hill (currently visiting on sabbatical, visiting ETH Zurich Mar-Jun)

Bivariate B-splines from Centroid Triangulations

This is work with Yuanxin (Leo) Liu, PhD candidate at UNC Chapel Hill.
Univariate B-splines are smooth, piecewise polynomial curves that can be defined on irregularly spaced points (called knots). Because they are also expressive -- they can reproduce all polynomials up to the desired degree -- they are often used in computer-aided geometric design (CAGD) and in function approximation.
All multivariate generalizations of B-splines proposed to date, with one exception, impose restrictions on knot placement -- to grids, tensor-product constructions, or multiple knots. The exception is Neamtu's elegant work, based on higher-order Voronoi diagrams, which we will describe. Even this has limitations when one wishes to consider data-dependent surface constructions because once the knot positions are chosen, their interconnection is fixed.
We observe that the essential property to prove polynomial reproduction in Neamtu's work is a combinatorial property that is satisfied by other triangulations. We propose a {\it link triangulation algorithm}, which dualizes and generalizes Lee's algorithm for higher order Voronoi diagrams, and guarantees the combinatorial property (and thus polynomial reproducability) for a wider class of triangulations.
We prove that the algorithm gives quadratic and cubic splines that include some of the classical multivariate splines. For example, we can use our algorithm to reproduce the classic quadratic box spline basis, the Zwart-Powell element, which means that we can use our splines to blend patches of quadratic box splines while preserving smoothness and polynomial reproducibility.


Faculty meeting

Letzte Aktualisierung: 17.04.2007