Kinetic convex hulls in the black-box model

Research output: Contribution to conferenceAbstractAcademic

76 Downloads (Pure)


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.
Original languageEnglish
Publication statusPublished - 2011
Event27th European Workshop on Computational Geometry (EuroCG 2011) - Morschach, Switzerland
Duration: 28 Mar 201130 Mar 2011
Conference number: 27


Workshop27th European Workshop on Computational Geometry (EuroCG 2011)
Abbreviated titleEuroCG


Dive into the research topics of 'Kinetic convex hulls in the black-box model'. Together they form a unique fingerprint.

Cite this