Kinetic spanners in Rd

M.A. Abam, M.T. Berg, de

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

2 Citations (Scopus)


We present a new (1+e)-spanner for sets of n points in Rd. Our spanner has size O(n/ed-1) and maximum degree O(logd n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n2/ed-1), and using a supporting data structure of size O(n logdn) we can handle events in time O(logd+1n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in Rd whose performance does not depend on the spread of the point set.
Original languageEnglish
Title of host publicationProceedings 25th Annual ACM Symposium on Computational Geometry (SoCG'09, Aarhus, Denmark, June 8-10, 2009)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
ISBN (Print)978-1-60558-501-7
Publication statusPublished - 2009


Dive into the research topics of 'Kinetic spanners in Rd'. Together they form a unique fingerprint.

Cite this