language: en

Probabilistic Analysis for Combinatorial Functions of Moving Points

Li Zhang Harish Devarajan Julien Basch Piotr Indyk
Computer Science Department Stanford University
Stanford, CA94305
flizhang,harish,jbasch,indykg@cs.stanford.edu September 9, 1997

Abstract Given a set of n points, what is the description complexity of their convex hull? In our world, this question is understood with an implicit "in the worst case", and the answer is n bd=2c where d is the dimension of the underlying space. This is not entirely satisfactory, as this description complexity can vary tremendously depending on the positions of the points. Another approach is to look at the expected description complexity when the points are drawn from a given distribution. This type of analysis, initiated by Renyi and Sulanke [RS63] and pursued by others gets its value from the fact that this expectation is in general much smaller than in the worst case, and, more importantly, in that it often allows one to design algorithms that have expected running times against which worst case aware algorithms cannot compete. For instance, the convex hull of n points drawn independently uniformly at random from a d-dimensional hypercube has expected complexity O(log d1 n), and can be computed in expected linear time. In parallel, in the past decade, a number of papers have considered a setting where points are allowed to move along low degree algebraic trajectories. Different questions have been asked in this context. In particular, Atallah [Ata85], studied the number of times the combinatorial description of the convex hull or closest pair can change, in the worst case ("dynamic computational geometry"). More recently, Basch, Guibas, and Hershberger [BGH97] have designed kinetic data structures to maintain these attributes in an online setting, measuring the quality of a kinetic data structure by the ratio of the worst case number of changes to the configuration of interest, to the worst case number of changes to the data structure itself, for low degree algebraic motions. However, an experimental study undertaken in [BGSZ97] to assess the quality of these data structures in practice shows that the worst case analysis can hide vastly different results in terms of expectation when the point positions and speeds are drawn at random from some distributions. It is this study that motivated the present paper. In this communication, we report several results on the expected number of changes to various combinatorial structures for the case when points are drawn from the uniform distribution on the unit square. These results can be generalized for any dimension d &gt; 2.

[This paper appeared in the]

[proceedings of the 13th Symposium of Computational Geometry (1997)]

[as a communication]

[Supported in part by National Science Foundation grant CCR-9623851 and by US Army MURI grant DAAH04-96-1-0007. Supported in part by the Okawa Foundation. x Supported in part by ARO MURI Grant DAAH04-96-1-0007 and by NSF Award CCR-9357849, with matching funds from IBM, Mitsubishi, Schlumberger Foundation, Shell Foundation, and Xerox Corporation.]