# Item

ITEM ACTIONSEXPORT

Released

Report

#### Dynamic algorithms for geometric spanners of small diameter: randomized solutions

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-94-156.pdf

(Any fulltext), 16MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Arya, S., Mount, D., & Smid, M.(1994). *Dynamic algorithms
for geometric spanners of small diameter: randomized solutions* (MPI-I-94-156). Saarbrücken: Max-Planck-Institut
für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B7A2-F

##### Abstract

Let $S$ be a set of $n$ points in $\IR^d$ and let $t>1$ be
a real number. A $t$-spanner for $S$ is a directed graph
having the points of $S$ as its vertices, such that for any
pair $p$ and $q$ of points there is a path from $p$ to $q$
of length at most $t$ times the Euclidean distance between
$p$ and $q$. Such a path is called a $t$-spanner path.
The spanner diameter of such a spanner is defined as the
smallest integer $D$ such that for any pair $p$ and $q$ of
points there is a $t$-spanner path from $p$ to $q$ containing
at most $D$ edges.
A randomized algorithm is given for constructing a
$t$-spanner that, with high probability, contains $O(n)$
edges and has spanner diameter $O(\log n)$.
A data structure of size $O(n \log^d n)$ is given that
maintains this $t$-spanner in $O(\log^d n \log\log n)$
expected amortized time per insertion and deletion, in the
model of random updates, as introduced by Mulmuley.
Previously, no results were known for spanners with low
spanner diameter and for maintaining spanners under insertions
and deletions.