## CompSci 269S, Spring 2007: Theory Seminar

### May 4, 2007, in Bren Hall 1423

# Region-Fault Tolerant Geometric Spanners

## M.A. Abam, M. de Berg, M. Farshi and J. Gudmundsson; appeared
in SODA 2007

## Presented by Kevin Wortman

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 *G* on a point set *P* and
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
*G*_{c}(*P*) - *F*, where
*G*_{c}(*P*) is the complete geometric graph on
*P*. We prove that any set *P* of *n* points admits a
*C*-fault tolerant (1+ε)-spanner of size
O(*n* log *n*) for any constant
ε > 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.