A framework for computing the greedy spanner

Q.W. Bouts, A.P. Brink, ten, K. Buchin

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

5 Citaten (Scopus)
81 Downloads (Pure)


The highest quality geometric spanner (e.g. in terms of edge count, both in theory and in practice) known to be computable in polynomial time is the greedy spanner. The state-of-the-art in computing this spanner are a O(n^2 log n) time, O(n^2) space algorithm and a O(n^2 log^2 n) time, O(n) space algorithm, as well as the `improved greedy' algorithm, taking O(n^3 log n) time in the worst case and O(n^2) space but being faster in practice thanks to a caching strategy. We identify why this caching strategy gives speedups in practice. We formalize this into a framework and give a general efficiency lemma. From this we obtain many new time bounds, both on old algorithms and on new algorithms we introduce in this paper. Interestingly, our bounds are in terms of the well-separated pair decomposition, a data structure not actually computed by the caching algorithms. Specifically, we show that the `improved greedy' algorithm has a O(n^2 log n log Phi) running time (where Phi is the spread of the point set) and a variation has a O(n^2 log^2 n) running time. We give a variation of the linear space state-of-the-art algorithm and an entirely new algorithm with a O(n^2 log n log Phi) running time, both of which improve its space usage by a factor O(1/(t-1)). We present experimental results comparing all the above algorithms. The experiments show that - when using low t - our new algorithm is up to 200 times more space efficient than the existing linear space algorithm, while being comparable in running time and much easier to implement.
Originele taal-2Engels
Titel30th ACM Symposium on Computational Geometry (SoCG, Kyoto, Japan, June 8-11, 2014)
Plaats van productieNew York NY
UitgeverijAssociation for Computing Machinery, Inc
ISBN van geprinte versie978-1-4503-2594-3
StatusGepubliceerd - 2014
Evenement30th Annual Symposium on Computational Geometry (SoCG 2014) - Kyoto, Japan
Duur: 8 jun 201411 jun 2014
Congresnummer: 30


Congres30th Annual Symposium on Computational Geometry (SoCG 2014)
Verkorte titelSoCG '14
Ander30th ACM Symposium on Computational Geometry

Vingerafdruk Duik in de onderzoeksthema's van 'A framework for computing the greedy spanner'. Samen vormen ze een unieke vingerafdruk.

Citeer dit