Processing math: 0%
Re­gion Span­ner for Disks
Michiel Smid
Car­leton Uni­ver­sity

Con­sider n pair­wise dis­joint disks. In­side any disk, we can travel at in­fi­nite speed, whereas out­side all disks, we can travel at speed one. The short­est travel times be­tween any pair of disks de­fines a met­ric space. I will pre­sent a (1+\varepsilon)-span­ner for this met­ric space hav­ing O(n/\varepsilon) edges. The span­ner is a nat­ural vari­ant of the Yao-graph.