Kinetic convex hulls and delaunay triangulations in the black-box model

Over the past decade, the kinetic-data-structures framework has become the standard in computational geometry for dealing with moving objects. A fundamental assumption underlying the framework is that the motions of the ob-jects are known in advance. This assumption severely limits the applicability of KDSs. We study KDSs in the black-box model, which is a hybrid of the KDS model and the tradi-tional time-slicing approach. In this more practical model we receive the position of each object at regular time steps and we have an upper bound on dmax, the maximum dis-placement of any point in one time step. We study the maintenance of the convex hull and the De-launay triangulation of a planar point set P in the black-box model, under the following assumption on dmax: there is some constant k such that for any point p ∈ P the disk of radius dmax contains at most k points. We analyze our algorithms in terms of ∆k, the so-called k-spread of P. We show how to update the convex hull at each time step in O(k∆k log 2 n) amortized time. For the Delaunay triangu-lation our main contribution is an analysis of the standard edge-flipping approach; we show that the number of flips is O(k2∆2k) at each time step