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

摘要

A spanner graph on a set of points in Ed provides shortest paths between any pair of points with lengths at most a constant factor of their Euclidean distance. A spanner with a sparse set of edges is thus a good candidate for network backbones, as in transportation networks and peer-to-peer network overlays. In this paper we investigate new models and aim to interpret why good spanners 'emerge' in reality, when they are clearly built in pieces by agents with their own interests and the construction is not coordinated. Our main result is to show that the following algorithm generates a (1 + e)-spanner with a linear number of edges. In our algorithm, the points build edges at an arbitrary order. A point p will only build an edge pq if there is no existing edge p'q' with p and q' at distances no more than 1/4(1+1/ε) ? pq from p, q respectively. Eventually when all points finish checking edges to all other points, the resulted collection of edges forms a sparse spanner as desired. As a side product, the spanner construction implies a greedy algorithm for constructing linear-size well-separated pair decompositions that may be of interest on its own.