Kinetic spanners in Rd

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.