An efficient method for finding the Delaunay triangulation of randomly scattered data with applications in contour plotting

This thesis contains an algorithm for finding the Delaunay triangulation of a set of randomly scattered points on a plane. The Delaunay triangulation is a set of triangles composed of edges connecting points which are nearest neighbors. The algorithm presented is guaranteed to run in time proportional to O(nlog(n)) in the worst case, which is asymptotically optimal as the number of points n increases. The definition and properties of the Delaunay triangulation and its relationship to the Voronoi partitioning are presented to introduce the problem. The difficulty of incomplete convertibility between Delaunay triangulation and Voronoi partitioning is discussed. The properties of the Delaunay triangulation pertinent to the development of an algorithm are developed in detail. An algorithm for finding the Delaunay triangulation is introduced in an overview of the necessary steps. A detailed discussion of the algorithm follows the overview and includes seventeen flowcharts. The method presented is either divide-and-conquer, or bottoms-up depending on the readers point of view. The algorithm discussed uses the circumcircle method of determining the correctness of the edges. The inherent problems of degenerate regions and triangulation consistency are resolved without resorting to inefficient techniques. Supporting algorithms and structures are also discussed in detail. Additional algorithms are provided for applying the Delaunay triangulation to the problem of contour mapping. Methods for creating 2D and 3D renderings are presented. Sample 3D output is presented in several rotations for gridded, rectangular random and polar random, point sets for a calculated function. A set of real world data 3D surface maps created using this algorithm are also presented. They illustrate that the surface created using the methods of this thesis preserves the detail and interpretability of the underlying data. This interpretability can be lost in other contouring methods.