# MPI-I-94-156

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

### Arya, Sunil and Mount, David and Smid, Michiel

**MPI-I-94-156**. December** **1994, ? pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-94-156.pdf | 15384 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-156

**BibTeX**
`@TECHREPORT{``AryaMountSmid94``,`

` AUTHOR = {Arya, Sunil and Mount, David and Smid, Michiel},`

` TITLE = {Dynamic algorithms for geometric spanners of small diameter: randomized solutions},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-94-156},`

` MONTH = {December},`

` YEAR = {1994},`

` ISSN = {0946-011X},`

`}`