Abam, Mohammad1; de Berg, Mark2; Gudmundsson, Joachim3
1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Eindhoven University3 National ICT Australia Ltd
We present a new and simple (1+ε)-spanner of size O(nε2) for a set of n points in the plane, which can be maintained efficiently as the points move. Assuming the trajectories of the points can be described by polynomials whose degrees are at most s, the number of topological changes to the spanner is O((n/ε2).λs+2(n)), and at each event the spanner can be updated in O(1) time.
Annual Symposium on Computational Geometry: Proceedings of the Twenty-fourth Annual Symposium on Computational Geometry, 2008, p. 306-310