The Delaunay triangulation is used extensively for representing geometric domains. Since its definition in 1934, researchers have applied it and its dual structure, the Voronoi diagram, to algorithms for surface reconstruction, mesh generation, simplification, and feature computation. Its universality can be explained by the mathematical properties it naturally optimizes, the provable guarantees it lends to algorithm analysis, and the design simplicity it provides for algorithms.

We consider the use of the Delaunay triangulation to approximate three different domains. We begin by developing a technique for simplifying vector field datasets using Delaunay triangulations. Piecewise-linear interpolation over Delaunay triangulations gives good approximations for scalar fields, motivating our approach on vector-valued data. We remove vertices from the Delaunay triangulation using a local error metric which is biased to preserve critical points of the field and to prevent topological changes during simplification. Experimental results show the effectiveness of this technique on both two and three dimensional datasets.

We next present an algorithm, DelIso, for building Delaunay meshes to approximate smooth surfaces defined by the isosurface of a volume datasets. DelIso employs a two stage algorithm which discards the need to maintain the full 3D Delaunay triangulation in the second stage. Implementation results have shown that by using this optimization we can obtain a 2-3 times speedup over its one stage counterpart. The resulting meshes are different from those produced by more common isosurfacing techniques (e.g. Marching Cubes) in that they are well graded and their topology is provably correct.

The third domain we investigate is piecewise smooth complexes (PSCs). We have designed DelPSC, an algorithm to build Delaunay meshes that approximate PSCs as well as the volumes contained within them. DelPSC was designed to be easily implementable, removing the need for many of the expensive computations that previously made Delaunay meshing for PSCs impractical. Its meshing strategy employs a protection scheme for sharp features that covers them with protecting balls whose radius mimics the feature size. Unfortunately, feature size computations can be costly, so we propose a novel protection method which first places balls along each curve and then iteratively shrinks them until they maintain a set of protection properties. We guarantee that with this set of protection properties our Delaunay refinement terminates and that by reducing a single scale parameter, the correct topology is achieved as well.

The approach used in DelPSC allows for meshing a wide variety of objects such as non-smooth CAD parts and non-manifold objects. We found with DelIso that Delaunay meshing for smooth surfaces could be adopted to mesh isosurfaces of volume datasets. Similarly, the strategy for Delaunay meshing of PSCs can be used to build meshes of the interface surfaces that multi-label volume datasets define. Our final contribution discusses the application of DelPSC to this form of data, commonly produced by segmenting MRI or CT datasets. We show the effectiveness of this technique on data from a variety of medical fields and discuss the its ability to control the quality and size of the output meshes.