Name
Abstract | ||
|---|---|---|
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(n2 log n) time, O(n2) space algorithm and a O(n2 log2 n) time, O(n) space algorithm, as well as the 'improved greedy' algorithm, taking O(n3 log n) time in the worst case and O(n2) 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(n2 log n log Φ) running time (where Φ is the spread of the point set) and a variation has a O(n2 log2 n) running time. We give a variation of the linear space state-of-the-art algorithm and an entirely new algorithm with a O(n2 log n log Φ) running time, both of which improve its space usage by a factor O(1/(t−1)), where t is the dilation of the spanner. We present experimental results comparing all the above algorithms. The experiments show that our new algorithm is much more space efficient than the existing linear space algorithm - up to 200 times when using low t - while being comparable in running time and much easier to implement. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2582112.2582154 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
n2 log2 n,n2 log n log,caching strategy,space algorithm,existing linear space algorithm,polynomial time,new time bound,new algorithm,greedy spanner,caching algorithm,factor o,computational geometry | Discrete mathematics,Binary logarithm,Combinatorics,Geometric spanner,Computational geometry,Linear space,Cache algorithms,Rabin–Karp algorithm,Time complexity,Spanner,Mathematics | Conference |
Citations | PageRank | References |
4 | 0.55 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Quirijn W. Bouts | 1 | 10 | 3.05 |
| Alex P. ten Brink | 2 | 6 | 1.27 |
| Kevin Buchin | 3 | 521 | 52.55 |