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

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

2009-05-15

arxiv.org/abs/0905.2605v2

Computer Science

Computational Geometry

Scientific paper

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 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 if edges are built in an arbitrary order but an edge is built if and only if its endpoints are not 'close' to the endpoints of an existing edge, the graph is a $(1 + \eps)$-spanner with a linear number of edges, constant average degree, and the total edge length as a small logarithmic factor of the cost of the minimum spanning tree. As a side product, we show a simple greedy algorithm for constructing optimal size well-separated pair decompositions that may be of interest on its own.

Affiliated with

Also associated with

No associations

Rating

The Emergence of Sparse Spanners and Greedy Well-Separated Pair Decomposition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Emergence of Sparse Spanners and Greedy Well-Separated Pair Decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Emergence of Sparse Spanners and Greedy Well-Separated Pair Decomposition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-524676