Shortest Paths in Unit Disk Graphs
Let $G$ be a unit disk graph in the plane defined by $n$ disks whose positions are known. For the case when $G$ is unweighted, we give a simple algorithm to compute a shortest path tree from a given source in $O(n \log n)$ time. For the case when $G$ is weighted, we show that a shortest path tree from a given source can be computed in $O(n^{1+ε})$ time, improving the previous best time bound of $O(n^{4/3+ε})$.