• Calendar

May 28, Tuesday
12:00 – 13:00

A {it Euclidean (1+eps)-spanner} for a point set S in the plane is a sparse subgraph H of the complete Euclidean graph corresponding to S, which preserves all pairwise distances to within a factor of 1+eps. Euclidean spanners constitute a fundamental graph structure as they can be used to approximately solve many geometric proximity problems. In many applications of Euclidean (1+eps)-spanners, in addition to being sparse, the spanners should achieve small {it weight}, {it maximum degree} and {it hop-diameter}. Understanding the inherent tradeoffs between these parameters is the foremost open question in this area. In this talk I will survey the previous state-of-the-art results, and then present our new constructions of optimal Euclidean spanners. If time permits, I will discuss extensions to {it doubling metrics} and to {it fault-tolerant spanners}, and present some open problems in this area.

The talk will be self-contained. It is based on my FOCS'08 paper (with Dinitz and Elkin), my SODA'11 paper, my STOC'13 paper (with Elkin), and my recent manuscript http://arxiv.org/abs/1304.8135