Dynamic Light Spanners in Doubling Metrics

Authors: Sujoy Bhore, Jonathan Conroy, Arnold Filtser Date: 2026-03-24 Paper ID: arxiv:2603.23490

Summary

This paper addresses the dynamic maintenance of a light-weight $t$-spanner for a set of points undergoing insertions and deletions in a metric space with a constant doubling dimension. The authors present an algorithm that maintains a $(1+\varepsilon)$-spanner whose total weight is bounded by a constant factor of the Minimum Spanning Tree (MST) weight. Each update operation (insertion or deletion) is performed in time polynomial in the logarithm of the aspect ratio ($\Phi$) of the point set. This work is significant as it provides the first efficient dynamic algorithm for maintaining a light-weight spanner, a problem for which no efficient solution was previously known, even in Euclidean space.

Key Contributions

• Development of the first efficient dynamic algorithm for maintaining a light-weight $(1+\varepsilon)$-spanner for a dynamic point set in a doubling metric space.
• Achieving an update time of $\operatorname{poly}(\log Φ)$ per insertion or deletion, where $\Phi$ is the aspect ratio of the point set.
• Guaranteeing that the total weight of the maintained $(1+\varepsilon)$-spanner is within a constant factor of the minimum spanning tree weight.
• Establishing a new baseline for dynamic spanner maintenance, where prior efficient methods were unknown even for Euclidean space.

Limitations

The update time depends polylogarithmically on the aspect ratio $\Phi$, which can be large for certain point distributions. The analysis is specific to metric spaces of constant doubling dimension.

Open Questions & Future Work

• dynamic-light-spanners-polylog-time
• dynamic-light-spanners-aspect-ratio-independence
• dynamic-light-spanners-d-exponent-independence

Limitations

The update time depends polylogarithmically on the aspect ratio $\Phi$, which can be large for certain point distributions. The analysis is specific to metric spaces of constant doubling dimension.

Links

• ArXiv Abstract
• PDF