Region-fault tolerant geometric spanners

M.A. Abam, M. Berg, de, M. Farshi, J. Gudmundsson

Research output: Contribution to journalArticleAcademicpeer-review

24 Citations (Scopus)

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 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 .
Original languageEnglish
Pages (from-to)556-582
JournalDiscrete and Computational Geometry
Volume41
Issue number4
DOIs
Publication statusPublished - 2009

Fingerprint

Dive into the research topics of 'Region-fault tolerant geometric spanners'. Together they form a unique fingerprint.

Cite this