Voronoi Diagrams and Convex Hulls of Random Moving Points

This report considers the expected combinatorial complexity of the Euclidean Voronoi diagram and the convex hull of sets of n independent random points moving in unit time between two positions drawn independently from the same distribution in R ^d for fixed d\ge 2 as n→∈fty . It is proved that, when the source and destination distributions are the uniform distribution on the unit d -ball, these complexities are Θ(n ^(d+1)/d ) for the Voronoi diagram and O(n ^(d-1)/(d+1) log n) for the convex hull. Additional results for the convex hull are O( log ^d n) for the uniform distribution in the unit d -cube and O( log ^(d+1)/2 n) for the d -dimensional normal distribution. Received November 23, 1998, and in revised form July 8, 1999.