Diploma Thesis

This section describes the results of my Diploma thesis I wrote as a visiting scholar at the University of California, Davis, from June 1st, 1998 to November 30th, 1999. The thesis was jointly supervised by Professor Hartmut Prautzsch, Institut für Betriebs- und Dialogsysteme, Fakultät für Informatik, Universität Karlsruhe (TH), Germany and Professor Bernd Hamann, Center for Image Processing and Integrated Computing (CIPIC), University of California, Davis.

Optimale Approximation uni- oder multivariater Funktionen in mehreren Auflösungen
aka
On Simulated Annealing And The Construction Of Linear Spline Approximations For Scattered Data

Abstract

We describe a method to create optimal linear spline approximations to arbitrary functions of one or two variables, given as scattered data without known connectivity. We start with an initial approximation consisting of a fixed number of vertices and improve this approximation by choosing different vertices, governed by a simulated annealing algorithm. In the case of one variable, the approximation is defined by line segments; in the case of two variables, the vertices are connected to define a Delaunay triangulation of the selected subset of sites in the plane. In a second version of this algorithm, specifically designed for the bivariate case, we choose vertex sets and also change the triangulation to achieve both optimal vertex placement and optimal triangulation. We then create a hierarchy of linear spline approximations, each one being a superset of all lower-resolution ones.

Pages In This Section

Download Section: You can download two different versions of a paper describing the algorithm and some examples, or you can download the complete thesis.
Approximation Examples: You can have a look at several multi-resolution approximations of different data sets, including a laser scan and several RGB images.
Virtual Gallery: If your browser is VRML-enabled, you can examine several multi-resolution approximations in a virtual reality environment. This is jolly good fun!
Approximation Programs: You can view the documentation of my approximation programs, and you can download pre-compiled versions for SGI workstations.