Complexity Analysis of Random Geometric Structures Made Simpler

Average-case analysis of data-structures or algorithms is com- monly used in computational geometry when the, more clas- sical, worst-case analysis is deemed overly pessimistic. Since these analyses are often intricate, the models of random geo- metric data that can be handled are often simplistic and far from "realistic inputs". We present a new simple scheme for the analysis of geometric structures. While this scheme only produces results up to a polylog factor, it is much simpler to apply than the classical techniques and therefore succeeds in analyzing new input distributions related to smoothed com- plexity analysis. We illustrate our method on two classical structures: con- vex hulls and Delaunay triangulations. Specifically, we give short and elementary proofs of the classical results that n points uniformly distributed in a ball in R^d have a convex hull and a Delaunay triangulation of respective expected d−1 complexities Θ(n^(d+1) ) and Θ(n). We then prove that if we start with n points well-spread on a sphere, e.g. an (epsilon,kappa)-sample of that sphere, and perturb that sample by moving each point randomly and uniformly within distance at most δ of its initial position, then the expected complexity of the convex hull of the resulting point set is Θ( n^(1/2-1/2d) δ^(-d/4+1/4d) ).