Region Spanner for Disks

Michiel Smid

Carleton University

Consider $n$ pairwise disjoint disks. Inside any disk, we can travel at infinite speed, whereas outside all disks, we can travel at speed one. The shortest travel times between any pair of disks defines a metric space. I will present a $(1+\varepsilon)$-spanner for this metric space having $O(n/\varepsilon)$ edges. The spanner is a natural variant of the Yao-graph.