Institute for Data Analysis and Visualization

We present a new algorithm for terrain modeling based on Voronoi diagrams and Sibson's inerpolant. Starting with a set of scattered sites in the plane with associated function values defining a height field, our algorithm constructs a top-down hierarchical representation. Sibson's interpolant is used to approximate the underlying height field based on the associated function values of selected subsets of the sites. Therefore, our algorithm constructs a hierarchy of Voronoi diagrams for nested subsets of the given sites. The quality of approximations obtained with our method compares favorably to results obtained from other multiresolution algorithms like wavelet transforms. For every level of resolution our approxiamations are C1 continuous, except at the selected sites, where only C[?] continuity is satisfied. Considering n sites, the expected time complexity of our algorithm is O (n log n) . In addition to a hierarchy based on convex cells and an importance ranking for sites.