The emergence of sparse spanners and greedy well-separated pair decomposition

Jie Gao, Dengpan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

A spanner graph on a set of points in ℝd 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 + ε)-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 from 1/4(1+1/ε)·|pq| form 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.

Original languageEnglish (US)
Title of host publicationAlgorithm Theory - SWAT 2010 - 12th Scandinavian Symposium and Workshops on Algorithm Theory, Proceedings
Pages50-61
Number of pages12
DOIs
StatePublished - 2010
Externally publishedYes
Event12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010 - Bergen, Norway
Duration: Jun 21 2010Jun 23 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6139 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010
Country/TerritoryNorway
CityBergen
Period6/21/106/23/10

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Greedy algorithm
  • Spanner
  • Well-separated pair decomposition

Fingerprint

Dive into the research topics of 'The emergence of sparse spanners and greedy well-separated pair decomposition'. Together they form a unique fingerprint.

Cite this