Fast approximating triangulation of large scattered datasets

This article describes algorithms and data-structures for the fast construc tion of three-dimensional triangulations from large sets of scattered data- points. The triangulations have a guaranteed error bound, i.e. all the data -points lie within a pre-specified distance from the triangulation. Three d ifferent methods for choosing triangulation vertices are presented, based o n interpolation, and L-2 and L infinity-optimization of the error over subs ets of the data-points. The main focus of this article will be on devising a simple and fast algorithm for constructing an approximating triangulation of a very large set of points. We propose the use of adapted dynamic data structures and excessive caching of information to speed up the computation and show how the method can be extended to approximate multiple dependent datasets in higher-dimensional approximation problems. (C) 1999 Elsevier Sc ience Ltd. All rights reserved.