Region-fault tolerant geometric spanners

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

6 Citaten (Scopus)


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 G on a point set P and a region F, we define G ¿ F to be what remains of G after the vertices and edges of G intersecting F have been removed. A C-fault tolerant t-spanner is a geometric graph G on P such that for any convex region F, the graph G ¿ F is a t-spanner for Gc(P)¿F, where Gc(P) is the complete geometric graph on P. We prove that any set P of n points admits a C-fault tolerant (1 + e)-spanner of size O(n log n), for any constant e > 0; if adding Steiner points is allowed then the size of the spanner reduces to O(n), and for several special cases we show how to obtain region-fault tolerant spanners of 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 G ¿ D between any two points u, v e 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 O(n) Steiner points to obtain a fault-tolerant geodesic (1 + e)-spanner of size O(n).
Originele taal-2Engels
TitelProceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007) 7-9 January 2007, New Orleans, Louisiana, USA
Plaats van productiePhiladephia PA
UitgeverijSociety for Industrial and Applied Mathematics (SIAM)
ISBN van geprinte versie978-0-898716-24-5
StatusGepubliceerd - 2007
Evenement18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007) - Astor Crowne Plaza Hotel, New Orleans, Verenigde Staten van Amerika
Duur: 7 jan 20079 jan 2007
Congresnummer: 18


Congres18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)
Verkorte titelSODA '07
LandVerenigde Staten van Amerika
StadNew Orleans
AnderSODA 2007, New orleans, Louisiana, USA


Duik in de onderzoeksthema's van 'Region-fault tolerant geometric spanners'. Samen vormen ze een unieke vingerafdruk.

Citeer dit