de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Dynamic algorithms for geometric spanners of small diameter: randomized solutions

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44034

Arya,  Sunil
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Mount,  David
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45509

Smid,  Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.