 |
|
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 ACM-SIAM 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