Topology preserving data simplification with error bounds

Many approaches to simplification of triangulated terrains and surfaces have been proposed which permit bounds on the error introduced. A few algorithms additionally bound errors in auxiliary functions defined over the triangulation. We present an approach to simplification of scalar fields over unstructured grids which preserves the topology of functions defined over the triangulation, in addition to bounding of the errors. The topology of a 2D scalar field is defined by critical points (local maxima, local minima, saddle points), in addition to integral curves between them, which together segment the field into regions which vary monotonically. By preserving this shape description, we guarantee that iso-contours of the scalar function maintain the correct topology in the simplified model. Methods for topology preserving simplification by both point-insertion (refinement) and point-deletion (coarsening) are presented and compared. (C) 1998 Elsevier Science Ltd. All rights reserved.