Peleg, David ;
Roditty, Liam
Relaxed Spanners for Directed Disk Graphs
Abstract
Let $(V,\delta)$ be a finite metric space, where $V$ is a set of
$n$ points and $\delta$ is a distance function defined for these
points. Assume that $(V,\delta)$ has a constant doubling dimension
$d$ and assume that each point $p\in V$ has a disk of radius
$r(p)$ around it. The disk graph that corresponds to $V$ and
$r(\cdot)$ is a \emph{directed} graph $I(V,E,r)$, whose vertices
are the points of $V$ and whose edge set includes a directed edge
from $p$ to $q$ if $\delta(p,q)\leq r(p)$. In~\cite{PeRo08} we
presented an algorithm for constructing a $(1+\eps)$spanner of
size $O(n/\eps^d \log M)$, where $M$ is the maximal radius $r(p)$.
The current paper presents two results. The first shows that the
spanner of~\cite{PeRo08} is essentially optimal, i.e., for metrics
of constant doubling dimension it is not possible to guarantee a
spanner whose size is independent of $M$. The second result shows
that by slightly relaxing the requirements and allowing a small
perturbation of the radius assignment, considerably better
spanners can be constructed. In particular, we show that if it is
allowed to use edges of the disk graph $I(V,E,r_{1+\eps})$, where
$r_{1+\eps}(p) = (1+\eps)\cdot r(p)$ for every $p\in V$, then it
is possible to get a $(1+\eps)$spanner of size $O(n/\eps^d)$ for
$I(V,E,r)$. Our algorithm is simple and can be implemented
efficiently.
BibTeX  Entry
@InProceedings{peleg_et_al:LIPIcs:2010:2489,
author = {David Peleg and Liam Roditty},
title = {{Relaxed Spanners for Directed Disk Graphs}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {609620},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2489},
URN = {urn:nbn:de:0030drops24898},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2489},
annote = {Keywords: Spanners, directed graphs}
}
Keywords: 

Spanners, directed graphs 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2010 
Date of publication: 

2010 