Computational geometric, combinatorial, and graph theoretic applications
Edward J. Wegman, Roger W. Shores · 2011
This dissertation deals with computational geometric, combinatorial, and graph theoretic applications to problems in statistics and computer networks. The first problem arises from multidimensional density estimation and data compression. The representation of data through tessellation, specifically Delaunay tessellation, is examined. The dissertation presents results about growth in the number of Delaunay tiles as a function of dimensionality and the number of observations, or points, used to construct the tessellation. It also establishes a relationship between vertex degree, a graph-theoretic concept, and tessellation count, a geometric concept. The second perspective is graph theory. The dissertation explores the application of Hamiltonian cycles in graphs and perfect matchings to computer network optimization. In that context, a discussion of the software developed to find all possible configurations of a graph for a given vertex degree distribution.