Maintaining light spanners via minimal updates.
D. Eppstein and
H. Khodabandeh.
arXiv:2403.03290.
Proc. 36th Canadian Conference on Computational Geometry, 2024, pp. 1–15.
We find a way to maintain a spanner of a dynamic point set, a graph approximating its distances to within a \(1+\varepsilon\) factor while maintaining weight proportionate to the minimum spanning tree. Each change to the point set leads to a logarithmic number of changes to the spanner, although update times remain slow.