Distribution-sensitive construction of the greedy spanner

S.P.A. Alewijnse, Q.W. Bouts, A.P. Brink, ten

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)


The greedy spanner is the highest quality geometric spanner (in e.g. edge count and weight, both in theory and practice) known to be computable in polynomial time. Unfortunately, all known algorithms for computing it on n points take O(n 2) time, limiting its use on large data sets. We observe that for many point sets, the greedy spanner has many ‘short’ edges that can be determined locally and usually quickly, and few or no ‘long’ edges that can usually be determined quickly using local information and the well-separated pair decomposition. We give experimental results showing large to massive performance increases over the state-of-the-art on nearly all tests and real-life data sets. On the theoretical side we prove a near-linear expected time bound on uniform point sets and a near-quadratic worst-case bound. Our bound for point sets drawn uniformly and independently at random in a square follows from a local characterization of t-spanners we give on such point sets: we give a geometric property that holds with high probability on such point sets. This property implies that if an edge set on these points has t-paths between pairs of points ‘close’ to each other, then it has t-paths between all pairs of points. This characterization gives a O(n log2 n log2 logn) expected time bound on our greedy spanner algorithm, making it the first subquadratic time algorithm for this problem on any interesting class of points. We also use this characterization to give a O((n¿+¿|E|) log2 n loglogn) expected time algorithm on uniformly distributed points that determines if E is a t-spanner, making it the first subquadratic time algorithm for this problem that does not make assumptions on E.
Originele taal-2Engels
TitelAlgorithms - ESA 2014 (22nd European Symposium on Algorithms, Wroclaw, Poland, September 8-10, 2014. Proceedings)
RedacteurenA.S. Schulz, D. Wagner
Plaats van productieBerlin
ISBN van geprinte versie978-3-662-44776-5
StatusGepubliceerd - 2014
Evenement22nd Annual European Symposium on Algorithms (ESA 2014) - Wrocław, Polen
Duur: 8 sep 201410 sep 2014
Congresnummer: 22

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Congres22nd Annual European Symposium on Algorithms (ESA 2014)
Verkorte titelESA 2014
Ander22nd European Symposium on Algorithms

Vingerafdruk Duik in de onderzoeksthema's van 'Distribution-sensitive construction of the greedy spanner'. Samen vormen ze een unieke vingerafdruk.

Citeer dit