Probabilistic analysis for combinatorial functions of moving points

Julien Basch, Harish Devarajan, Piotr Indyk, and Li Zhang


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.
  • Proceedings of the 12th ACM-SIAM symposium on computational geometry, ...
  • Presented at the 2nd CGC workshop, Duke university, 1997
  • Submitted to IJCGA