Kinetic spanners in R d
Mohammad Ali Abam, Mark de Berg · 2009
We present a new (1+ε)-spanner for sets of n points in Rd. Our spanner has size O(n/εd-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/εd-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.