We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Region-Fault Tolerant Geometric Spanners.
- Authors
Abam, M. A.; de Berg, M.; Farshi, M.; Gudmundsson, J.
- Abstract
We introduce the concept of region-fault tolerant spanners for planar point sets and prove the existence of region-fault tolerant spanners of small size. For a geometric graph $\mathcal{G}$ on a point set P and a region F, we define $\mathcal{G}\ominus F$ to be what remains of $\mathcal{G}$ after the vertices and edges of $\mathcal{G}$ intersecting F have been removed. A $\mathcal{C}$ - fault tolerant t- spanner is a geometric graph $\mathcal{G}$ on P such that for any convex region F, the graph $\mathcal{G}\ominus F$ is a t-spanner for $\mathcal{G}_{c}(P)\ominus F$ , where $\mathcal{G}_{c}(P)$ is the complete geometric graph on P. We prove that any set P of n points admits a $\mathcal{C}$ -fault tolerant (1+ ε)-spanner of size $\mathcal{O}(n\log n)$ for any constant ε>0; if adding Steiner points is allowed, then the size of the spanner reduces to $\mathcal{O}(n)$ , and for several special cases, we show how to obtain region-fault tolerant spanners of $\mathcal{O}(n)$ size without using Steiner points. We also consider fault-tolerant geodesic t -spanners: this is a variant where, for any disk D, the distance in $\mathcal{G}\ominus D$ between any two points u, v∈ P∖ D is at most t times the geodesic distance between u and v in ℝ2∖ D. We prove that for any P, we can add $\mathcal{O}(n)$ Steiner points to obtain a fault-tolerant geodesic (1+ ε)-spanner of size $\mathcal{O}(n)$ .
- Subjects
WRENCHES; GEOMETRY; FAULT tolerance (Engineering); GEODESICS; CONVEX domains; GRAPHIC methods
- Publication
Discrete & Computational Geometry, 2009, Vol 41, Issue 4, p556
- ISSN
0179-5376
- Publication type
Article
- DOI
10.1007/s00454-009-9137-7