Kinetic spanners in Rd

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

Research output: Contribution to journalArticleAcademicpeer-review

15 Citations (Scopus)
87 Downloads (Pure)


We present a new $(1 + \epsilon)$-spanner for sets of $n$ points in $\mathbb{R}^d$. Our spanner has size $O(n/\epsilon^{d-1})$ and maximum degree $O(\log^d n)$. The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming that the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is $O(n^2/\epsilon^{d-1})$, and using a supporting data structure of size $O(n\log^d n)$, we can handle events in time $O(\log^{d+1} n)$. 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 $\mathbb{R}^d$ whose performance does not depend on the spread of the point set.
Original languageEnglish
Pages (from-to)723-736
JournalDiscrete and Computational Geometry
Issue number4
Publication statusPublished - 2011


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

Cite this