Maintaining Light Spanners via Minimal Updates
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910354801426432 |
|---|---|
| author | Khodabandeh, Hadi Eppstein, David |
| author_facet | Khodabandeh, Hadi Eppstein, David |
| contents | We study the problem of maintaining a lightweight bounded-degree $(1+\varepsilon)$-spanner of a dynamic point set in a $d$-dimensional Euclidean space, where $\varepsilon>0$ and $d$ are arbitrary constants. In our fully-dynamic setting, points are allowed to be inserted as well as deleted, and our objective is to maintain a $(1+\varepsilon)$-spanner that has constant bounds on its maximum degree and its lightness (the ratio of its weight to that of the minimum spanning tree), while minimizing the recourse, which is the number of edges added or removed by each point insertion or deletion. We present a fully-dynamic algorithm that handles point insertion with amortized constant recourse and point deletion with amortized $O(\logΔ)$ recourse, where $Δ$ is the aspect ratio of the point set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_03290 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Maintaining Light Spanners via Minimal Updates Khodabandeh, Hadi Eppstein, David Computational Geometry Data Structures and Algorithms We study the problem of maintaining a lightweight bounded-degree $(1+\varepsilon)$-spanner of a dynamic point set in a $d$-dimensional Euclidean space, where $\varepsilon>0$ and $d$ are arbitrary constants. In our fully-dynamic setting, points are allowed to be inserted as well as deleted, and our objective is to maintain a $(1+\varepsilon)$-spanner that has constant bounds on its maximum degree and its lightness (the ratio of its weight to that of the minimum spanning tree), while minimizing the recourse, which is the number of edges added or removed by each point insertion or deletion. We present a fully-dynamic algorithm that handles point insertion with amortized constant recourse and point deletion with amortized $O(\logΔ)$ recourse, where $Δ$ is the aspect ratio of the point set. |
| title | Maintaining Light Spanners via Minimal Updates |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.03290 |