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.