Average-case analysis of algorithms for convex hulls and voronoi diagrams

This thesis addressed the design and analysis of fast-on-average algorithms for two classic problems of computational geometry: the construction of convex hulls and Voronoi diagrams of finite point sets in Euclidean d-space.; The main contributions of the thesis are: (1) A new algorithm for enumerating ther vertices of a convex hull that requires between {dollar}Theta{dollar}(n) and {dollar}Theta{dollar}(n{dollar}sp2{dollar}) time on average for a set of n independent and identically distributed (i.i.d.) points. The exact running time depends on the input distribution. This algorithm is a useful preprocessing step for algorithms for the facet-enumeration and facial-lattice versions of the convex-hull problem. (2) A new method for bounding the expected number of vertices of the convex hull of random points, new results on the asymptotic behavior of the expected number of vertices and facets of the convex hull of n i.i.d. points drawn from any of a wide variety of input distributions in d dimensions, and application of these results to the analysis of existing convex-hull algorithms. The distributions considered are: spherically symmetric distributions with algebraic, exponential, and truncated tails; certain uniform product distributions; and uniform distributions in d-polytopes. For all but the product distributions, it is shown that two well-known convex-hull algorithms require o(n{dollar}sp2{dollar}) time on average; for some of the distributions, linear time suffices. (3) A new method for analyzing the expected combinatorial complexity and other properties of a random Voronoi diagram in d dimensions, and new results on the expected complexity of the Voronoi diagram of n points chosen from the uniform distribution in the unit d-ball. (4) A new linear-expected-time algorithm for constructing the Voronoi diagram of n points from the uniform distribution in the unit d-ball. (5) A practical improvement to the classic divide-and-conquer algorithm for the two-dimensional Voronoi diagram that decreases its average running time from {dollar}Theta{dollar}(n log n) to {dollar}Theta{dollar}(n log log n) for n points from the uniform distribution in the unit square and similar distributions.