Kinetic convex hulls 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 objects 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 traditional 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 d_max, the maximum displacement of any point in one time step. We study the maintenance of the convex hull of a planar point set P in the black-box model, under the following assumption on d_max: there is some constant k such that for any point p in P the disk of radius d_max contains at most k points. We analyze our algorithms in terms of \Delta_k, the so-called k-spread of P. We show how to update the convex hull at each time step in O(k \Delta_k log^2 n) amortized time.