We describe the algorithms and data structures used for optimizing linear spline approximations of bivariate functions. Our method creates a random initial triangulation of a given data set and then employs a simulated annealing algorithm to improve this initial approximation. In every iteration step, the current approximation is changed in a random but local way, and the distance measure between it and the data is re-calculated. Depending on the difference between the old and new distance measures, an iteration step is either accepted or rejected.We discuss the basic operations and data structures of our optimization technique. We present a variant of the half-edge data structure and associated algorithms.

Multiresolution representation of high-dimensional scattered data is a fundamental problem in scientific visualization. This paper introduces a data hierachy of Voronoi diagrams as a versatile solution. Given an arbitrary set of points in the plane, our goal is the construction of an approximation hierarhy using the Voronoi diagram as the essential building block. We have implemented two Voronoi diagram-based algorithms to demonstrate their usefulness for hierarchical scattered data approximation. The first algorithm uses a constant function to approximate the data within each Voronoi cell, and the second algorithm uses the Sibson interpolant [14].