2009.04.14 | Else Magård

Title: Kinetic spanner
Speaker: Mohammad Ali Abam, Aarhus University

Abstract:

We present a new $(1+\\eps)$-spanner for sets of $n$ points in $\\Reals^d$.
Our spanner has size $O(n/\\eps^{d-1})$ and maximum degree $O(\\log^d n)$.

The main advantage of our spanner is thatit 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 changesto the spanner is $O(n^2/\\eps^{d-1})$, and using a supporting data structure of size $O(n\\log^{d}n)$ we can handleevents in time $O(\\log^{d+1} n)$. Moreover, the spanner can be updated in time $O(\\log n)$ if the flight plan of apoint changes.

This is the first kinetic spanner for points in $\\Reals^d$ whose performance does not depend on the spread of the point set.

Host: Gerth Stølting Brodal