Abstract
A disk graph is an intersection graph of a set of disks with arbitrary radii in the plane. In this paper, we consider the problem of efficient construction of sparse spanners of disk (ball) graphs with support for fast distance queries. These problems are motivated by issues arising from topology control and routing in wireless networks.
We present the first algorithm for constructing spanners of ball graphs. For a ball graph in 
, we construct a (1 + ε)-spanner with O(nε
− k + 1) edges in O(n
2ℓ + δ
ε
− k logℓ
S) expected time, using an efficient partitioning of the space into hypercubes and solving intersection problems. Here \(\ell=1-1/(\lfloor k/2 \rfloor+2)\), δ is any positive constant, and S is the ratio between the largest and smallest radius. For the special case where all the balls have the same radius, we show that the spanner construction has complexity almost equivalent to the construction of a Euclidean minimum spanning tree. Previously known constructions of spanners of unit ball graphs have time complexity much closer to n
2. Additionally, these spanners have a small vertex separator (hereditary), which is then exploited for fast answering of distance queries. The results on geometric graph separators might be of independent interest.
A short abstract of this work appeared in the proceedings of FWCG 2006.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Eppstein, D.: Testing bipartiteness of geometric intersection graphs. In: SODA 2004, SIAM, pp. 860–868 (2004)
Rajaraman, R.: Topology control and routing in ad hoc networks: A survey. SIGACT News 33, 60–73 (2002)
Li, X.Y.: Algorithmic, geometric and graphs issues in wireless networks. Wireless Communications and Mobile Computing 3(2), 119–140 (2003)
Erickson, J.: On the relative complexities of some geometric problems. In: CCCG 1995, pp. 85–90 (1995)
Yao, A.C.C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing 11(4), 721–736 (1982)
Agarwal, P.K., Edelsbrunner, H., Schwarzkopf, O., Welzl, E.: Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Computational Geometry 6, 407–422 (1991)
Gao, J., Zhang, L.: Well-separated pair decomposition for the unit-disk graph metric and its applications. SIAM Journal on Computing 35(1), 151–169 (2005)
Gudmundsson, J.: Constructing sparse t-spanners with small separators. In: Lingas, A., Nilsson, B.J. (eds.) FCT 2003. LNCS, vol. 2751, pp. 86–97. Springer, Heidelberg (2003)
Gudmundsson, J.: Personal communication (2006)
Fürer, M., Kasiviswanathan, S.P.: Approximate distance queries in disk graphs. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol. 4368, pp. 174–187. Springer, Heidelberg (2007)
Agarwal, P.K., Matoušek, J.: Dynamic half-space range reporting and its applications. Algorithmica 13(4), 325–345 (1995)
Fürer, M., Kasiviswanathan, S.P.: Spanners for geometric intersection graphs (2007), Available at http://www.cse.psu.edu/~kasivisw/spanner.pdf
Ruppert, J., Seidel, R.: Approximating the d-dimensional complete euclidean graph. In: CCCG 1991, pp. 207–210 (1991)
Bose, P., Maheshwari, A., Narasimhan, G., Smid, M.H.M., Zeh, N.: Approximating geometric bottleneck shortest paths. Comput. Geom 29(3), 233–249 (2004)
Lukovszki, T.: New results on geometric spanners and their applications. PhD. thesis, University of Paderborn (1999)
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(1), 67–90 (1995)
Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: SODA 1993, SIAM, pp. 291–300 (1993)
Smid, M.: The well-separated pair decomposition and its applications. In: Gonzalez, T. (ed.) Handbook on Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC (to appear)
Har-Peled, S.: Approximation algorithms in geometry. Available at: http://valis.cs.uiuc.edu/~sariel/research/book/aprx/
Bern, M.W., Eppstein, D., Teng, S.H.: Parallel construction of quadtrees and quality triangulations. Int. J. Computational Geometry & Applications 9(6), 517–532 (1999)
Gupta, P., Janardan, R., Smid, M.: Algorithms for some intersection searching problems involving circular objects. International Journal of Mathematical Algorithms 1, 35–52 (1999)
Chan, T.M.: Geometric applications of a randomized optimization technique. Discrete & Computational Geometry 22(4), 547–567 (1999)
Krznaric, D., Levcopoulos, C., Nilsson, B.J.: Minimum spanning trees in d dimensions. Nord. J. Comput. 6(4), 446–461 (1999)
Arikati, S.R., Chen, D.Z., Chew, L.P., Das, G., Smid, M.H.M., Zaroliagis, C.D.: Planar spanners and approximate shortest path queries among obstacles in the plane. In: Díaz, J. (ed.) ESA 1996. LNCS, vol. 1136, pp. 514–528. Springer, Heidelberg (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fürer, M., Kasiviswanathan, S.P. (2007). Spanners for Geometric Intersection Graphs. In: Dehne, F., Sack, JR., Zeh, N. (eds) Algorithms and Data Structures. WADS 2007. Lecture Notes in Computer Science, vol 4619. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73951-7_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-73951-7_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73948-7
Online ISBN: 978-3-540-73951-7
eBook Packages: Computer ScienceComputer Science (R0)