Region-fault tolerant geometric spanners
Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson · TU/e Research Portal · 2007
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 .