Loading...
Please wait, while we are loading the content...
Similar Documents
The Emergence of Sparse Spanners and Greedy Well-Separated Pair Decomposition
| Content Provider | arXiv |
|---|---|
| Author | Gao, Jie Zhou, Dengpan |
| Date of Submission | 2009-05-15 |
| Abstract | 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. |
| Related Links | https://arxiv.org/pdf/0905.2605.pdf |
| arXiv | 0905.2605 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Computational Geometry Computer Science - Data Structures and Algorithms Computer Science |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
