An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Bruce W. Brewer, Haitao Wang

Given in the plane a set $S$ of $n$ points and a set of disks centered at these points, the disk graph $G(S)$ induced by these disks has vertex set $S$ and an edge between two vert…