Average-case analysis of algorithms for convex hulls and Voronoi diagrams
Rex A. Dwyer · 1988
This thesis addresses 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: • A new algorithm for enumerating the vertices of a convex hull that requires between O(n) and O(n 2) 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. • 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