A simple and efficient kinetic spanner

M.A. Abam, M. Berg, de, J. Gudmundsson

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

2 Citations (Scopus)

Abstract

We present a new and simple (1+e)-spanner of size O(ne2) for a set of n points in the plane, which can be maintained efficiently as the points move. Assuming the trajectories of the points can be described by polynomials whose degrees are at most s, the number of topological changes to the spanner is O((n/e2).¿s+2(n)), and at each event the spanner can be updated in O(1) time.
Original languageEnglish
Title of host publicationProceedings 24th Annual ACM Symposium on Computational Geometry (SoCG'08, College Park MD, USA, June 9-11, 2008)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages306-310
ISBN (Print)978-1-60558-071-5
DOIs
Publication statusPublished - 2008

Fingerprint Dive into the research topics of 'A simple and efficient kinetic spanner'. Together they form a unique fingerprint.

Cite this