
Julien Basch, Harish Devarajan, Piotr Indyk, and Li Zhang
Abstract:
We initiate a probabilistic study of configuration functions of moving points, and of kinetic data structures. In our probabilistic model, a particle is given an initial position and a velocity drawn independently at random from the same distribution ${\cal D}$. We show that if n particles are drawn independently at random from the uniform distribution on the square, their convex hull undergoes $\Theta(\log^2 n)$ combinatorial changes in expectation, their Voronoi diagram undergoes $\Theta(n^{3/2})$ combinatorial changes, and their closest pair undergoes $\Theta(n)$ combinatorial changes.References:
 Proceedings of the 12th ACMSIAM symposium on computational geometry, ...
 Presented at the 2nd CGC workshop, Duke university, 1997
 Submitted to IJCGA
 Poster from SoCG 97
 Short communication from SoCG 97
 Full version, International Journal of Computational Geometry and Applications, 2001