Kinetic convex hulls in the black-box model

Onderzoeksoutput: Bijdrage aan congresAbstractAcademic

39 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.
Originele taal-2Engels
StatusGepubliceerd - 2011
Evenement27th European Workshop on Computational Geometry (EuroCG 2011) - Morschach, Zwitserland
Duur: 28 mrt 201130 mrt 2011
Congresnummer: 27


Workshop27th European Workshop on Computational Geometry (EuroCG 2011)
Verkorte titelEuroCG

Vingerafdruk Duik in de onderzoeksthema's van 'Kinetic convex hulls in the black-box model'. Samen vormen ze een unieke vingerafdruk.

Citeer dit