TY - JOUR

T1 - Region-fault tolerant geometric spanners

AU - Abam, M.A.

AU - Berg, de, M.

AU - Farshi, M.

AU - Gudmundsson, J.

PY - 2009

Y1 - 2009

N2 - 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 on a point set P and a region F, we define to be what remains of after the vertices and edges of intersecting F have been removed. A -fault tolerant t-spanner is a geometric graph on P such that for any convex region F, the graph is a t-spanner for , where is the complete geometric graph on P. We prove that any set P of n points admits a -fault tolerant (1+e)-spanner of size for any constant e>0; if adding Steiner points is allowed, then the size of the spanner reduces to , and for several special cases, we show how to obtain region-fault tolerant spanners of 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 between any two points u,v¿P\D is at most t times the geodesic distance between u and v in R2\D. We prove that for any P, we can add Steiner points to obtain a fault-tolerant geodesic (1+e)-spanner of size .

AB - 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 on a point set P and a region F, we define to be what remains of after the vertices and edges of intersecting F have been removed. A -fault tolerant t-spanner is a geometric graph on P such that for any convex region F, the graph is a t-spanner for , where is the complete geometric graph on P. We prove that any set P of n points admits a -fault tolerant (1+e)-spanner of size for any constant e>0; if adding Steiner points is allowed, then the size of the spanner reduces to , and for several special cases, we show how to obtain region-fault tolerant spanners of 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 between any two points u,v¿P\D is at most t times the geodesic distance between u and v in R2\D. We prove that for any P, we can add Steiner points to obtain a fault-tolerant geodesic (1+e)-spanner of size .

U2 - 10.1007/s00454-009-9137-7

DO - 10.1007/s00454-009-9137-7

M3 - Article

VL - 41

SP - 556

EP - 582

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 4

ER -