2026-07-20T05:58:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25819 2026-06-23T12:58:58Z ddc:004 open_access

Dynamic Light Spanners in Doubling Metrics Bhore, Sujoy Conroy, Jonathan Filtser, Arnold Dynamic data structures spanners light-weight Euclidean metrics doubling metrics A t-spanner of a point set X in a metric space (𝒳, δ) is a graph G with vertex set P such that, for any pair of points u,v ∈ X, the distance between u and v in G is at most t times δ(u,v). We study the problem of maintaining a spanner for a dynamic point set X - that is, when X undergoes a sequence of insertions and deletions - in a metric space of constant doubling dimension. For any constant ε > 0, we maintain a (1+ε)-spanner of P whose total weight remains within a constant factor of the weight of the minimum spanning tree of X. Each update (insertion or deletion) can be performed in poly(log Φ) time, where Φ denotes the aspect ratio of X. Prior to our work, no efficient dynamic algorithm for maintaining a light-weight spanner was known even for point sets in low-dimensional Euclidean space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sujoy Bhore and Jonathan Conroy and Arnold Filtser 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.13 urn:nbn:de:0030-drops-258193 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.13 eng https://creativecommons.org/licenses/by/4.0/legalcode