We present a new (1+e)-spanner for sets of n points in Rd. Our spanner has size O(n/ed-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/ed-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.
|Title of host publication||Proceedings 25th Annual ACM Symposium on Computational Geometry (SoCG'09, Aarhus, Denmark, June 8-10, 2009)|
|Place of Publication||New York NY|
|Publisher||Association for Computing Machinery, Inc|
|Publication status||Published - 2009|