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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)
263 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 dmax, the maximum displacement of any point in one time step. We study the maintenance of the convex hull and the Delaunay 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 log2 n) amortized time. For the Delaunay triangulation our main contribution is an analysis of the standard edge-flipping approach; we show that the number of flips is O(k2 ¿k2) at each time step.
Original languageEnglish
Title of host publicationProceedings 27th Annual ACM Symposium on Computational Geometry (SoCG'11, Paris, France, June 13-15, 2011)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
ISBN (Print)978-1-4503-0682-9
Publication statusPublished - 2011


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

Cite this