Probabilistic analysis for combinatorial functions of moving points
Li Zhang, Harish Devarajan, Julien Basch, Piotr Indyk · 1997
We initiate a probabilistic study of configuration functions of moving points.In our probabilistic model, a particle is given an initiaf position and a velocity drawn independently at random from the same distribution D. We show that if n particles are drawn independently at random from the uniform distribution on the square, their convex hull undergoes El(logz n) combinatorial changes in expectation, their Voronoi diagram undergoes e(n312 ) combinatorial changes, and their closest pair undergoes El(n) combinatorial changes.