# Relaxed spanners for directed disk graphs

* Auteur correspondant
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.
Keywords :
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.609-620, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Domaine :

Littérature citée [11 références]

https://hal.inria.fr/inria-00455800
Contributeur : Publications Loria <>
Soumis le : jeudi 11 février 2010 - 11:34:01
Dernière modification le : jeudi 11 février 2010 - 12:59:01
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:13:20

### Fichier

peleg.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00455800, version 1

### Citation

David Peleg, Liam Roditty. Relaxed spanners for directed disk graphs. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.609-620, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455800〉

### Métriques

Consultations de la notice

## 129

Téléchargements de fichiers