Skip to main content
Open Access Publications from the University of California

Terrain Modeling Using Voronoi Hierachies


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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View