Computing the Greedy Spanner in Near-Quadratic Time
Tóm tắt
The greedy algorithm produces high-quality spanners and, therefore, is used in several applications. However, even for points in d-dimensional Euclidean space, the greedy algorithm has near-cubic running time. In this paper, we present an algorithm that computes the greedy spanner for a set of n points in a metric space with bounded doubling dimension in
$\ensuremath {\mathcal {O}}(n^{2}\log n)$
time. Since computing the greedy spanner has an Ω(n
2) lower bound, the time complexity of our algorithm is optimal within a logarithmic factor.
Tài liệu tham khảo
Althöfer, I., Das, G., Dobkin, D.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9(1), 81–100 (1993)
Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42, 67–90 (1995)
Chandra, B.: Constructing sparse spanners for most graphs in higher dimensions. Inf. Process. Lett. 51(6), 289–294 (1994)
Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. Int. J. Comput. Geom. Appl. 5, 124–144 (1995)
Chew, L.P.: There is a planar graph almost as good as the complete graph. In: SCG’86: Proceedings of the 2nd Annual ACM Symposium on Computational Geometry, pp. 169–177 (1986)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press/McGraw-Hill, Cambridge/New York (2001)
Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geom. Appl. 7, 297–315 (1997)
Das, G., Heffernan, P.J., Narasimhan, G.: Optimally sparse spanners in 3-dimensional Euclidean space. In: SCG’93: Proceedings of the 9th Annual ACM Symposium on Computational Geometry, pp. 53–62 (1993)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959)
Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 425–461. Elsevier, Amsterdam (2000)
Farshi, M.: A theoretical and experimental study of geometric networks. Ph.D. Thesis, Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands (2008)
Farshi, M., Gudmundsson, J.: Experimental study of geometric t-spanners. In: ESA’05: Proceedings of the 13th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 3669, pp. 556–567. Springer, Berlin (2005)
Farshi, M., Gudmundsson, J.: Experimental study of geometric t-spanners: A running time comparison. In: WEA’07: Proceedings of the 6th Workshop on Experimental Algorithms. Lecture Notes in Computer Science, vol. 4525, pp. 270–284. Springer, Berlin (2007)
Gudmundsson, J., Knauer, C.: Dilation and detour in geometric networks. In: Gonzalez, T. (ed.) Handbook on Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC Press, London/Boca Raton (2007)
Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Improved greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31(5), 1479–1500 (2002)
Har-Peled, S.: A simple proof? http://valis.cs.uiuc.edu/blog/?p=441 (2006)
Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35(5), 1148–1184 (2006)
Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)
Peleg, D., Schäffer, A.: Graph spanners. J. Graph Theory 13, 99–116 (1989)
Russel, D., Guibas, L.J.: Exploring protein folding trajectories using geometric spanners. In: Pacific Symposium on Biocomputing, pp. 40–51 (2005)
Smid, M.: Closest point problems in computational geometry. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 877–935. Elsevier, Amsterdam (2000)
Soares, J.: Approximating Euclidean distances by small degree graphs. Discrete Comput. Geom. 11, 213–233 (1994)
Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: STOC’04: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 281–290. ACM, New York (2004)