The Emergence of Sparse Spanners and Greedy Well-Separated Pair Decomposition

Jie Gao, Dengpan Zhou

A spanner graph on a set of points in $R^d$ contains a shortest path between any pair of points with length at most a constant factor of their Euclidean distance. In this paper we…