PROBABILISTIC ANALYSIS FOR DISCRETE ATTRIBUTES OF MOVING POINTS
Julien Basch, HARISH DEVARAJAN, Piotr Indyk, Zhang Li · International Journal of Computational Geometry & Applications · 2003
We perform a probabilistic study of discrete attributes of moving points. In our probabilistic model, an item is given an initial position and a velocity drawn independently at random from the same distribution. We study the expected number of changes that happen to the closest pair, the Voronoi diagram, and the convex hull of a set of such moving items.