×

On a family of strong geometric spanners that admit local routing strategies. (English) Zbl 1408.05092

Summary: We introduce a family of directed geometric graphs, whose vertices are points in \({\mathbb{R}}^d\). The graphs \(G^\theta_\lambda\) in this family depend on two real parameters \(\lambda \) and \(\theta\). For \(\frac{1}{2} < \lambda < 1\) and \(\frac {\pi}{3} < \theta < \frac{\pi}{2}\), the graph \(G^\theta_\lambda\) is a strong \(t\)-spanner for \(t = \frac{1}{(1-\lambda)\cos\theta}\). That is, for any two vertices \(p\) and \(q\), \(G^\theta_\lambda\) contains a path from \(p\) to \(q\) of length at most \(t\) times the Euclidean distance \(|pq|\), and all edges on this path have length at most \(|pq|\). The out-degree of any node in the graph \(G^\theta_\lambda\) is \(O(1/\phi^{d-1})\), where \(\phi = \min(\theta,\arccos\frac{1}{2\lambda})\). We show that routing on \(G^\theta_\lambda\) can be achieved locally. Finally, we show that all strong \(t\)-spanners are also \(t\)-spanners of the unit-disk graph.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C75 Structural characterization of families of graphs
05C85 Graph algorithms (graph-theoretic aspects)
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI

References:

[1] Barbeau, M.; Kranakis, E., Principles of Ad Hoc Networking (2007), Wiley
[2] Bose, P.; Devroye, L.; Evans, W.; Kirkpatrick, D., On the spanning ratio of Gabriel graphs and \(β\)-skeletons, SIAM J. Discrete Math., 20, 2, 412-427 (2006) · Zbl 1115.68107
[3] Bose, P.; Brodnik, A.; Carlsson, S.; Demaine, E.; Fleischer, R.; Lopez, A.; Morin, P.; Munro, I., Online routing in convex subdivisions, Int. J. Comput. Geom. Appl., 12, 4, 283-295 (2002) · Zbl 1152.68478
[4] Bose, P.; Maheshwari, A.; Narasimhan, G.; Smid, M.; Zeh, N., Approximating geometric bottleneck shortest paths, Comput. Geom. Theory Appl., 29, 3, 233-249 (2004) · Zbl 1082.65015
[5] Bose, P.; Morin, P., Online routing in triangulations, SIAM J. Comput., 33, 4, 937-951 (2004) · Zbl 1061.65014
[6] Cardinal, J.; Collette, S.; Langerman, S., Empty region graphs, Comput. Geom. Theory Appl., 42, 3, 183-195 (2009) · Zbl 1161.05314
[7] Chávez, E.; Dobrev, S.; Kranakis, E.; Opatrny, J.; Stacho, L.; Tejeda, H.; Urrutia, J., Half-space proximal: A new local test for extracting a bounded dilation spanner of a unit disk graph, (Proceedings of the 9th International Conference on Principles of Distributed Systems (OPODIS 05). Proceedings of the 9th International Conference on Principles of Distributed Systems (OPODIS 05), Lecture Notes in Computer Science, vol. 3974 (2006), Springer-Verlag), 235-245
[8] Keil, J. M.; Gutwin, C. A., Classes of graphs which approximate the complete Euclidean graph, Discrete Comput. Geom., 7, 1, 13-28 (1992) · Zbl 0751.52004
[9] E. Kranakis, H. Singh, J. Urrutia, Compass routing on geometric networks, in: Proc. of Canadian Conf. on Comp. Geom., 1999, pp. 51-54.; E. Kranakis, H. Singh, J. Urrutia, Compass routing on geometric networks, in: Proc. of Canadian Conf. on Comp. Geom., 1999, pp. 51-54.
[10] Li, X.-Y., Wireless Ad Hoc and Sensor Networks (2008), Cambridge University Press: Cambridge University Press New York, NY, USA
[11] Narasimhan, G.; Smid, M., Geometric Spanner Networks (2007), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 1140.68068
[12] Yao, A. C.-C., On constructing minimum spanning trees in \(k\)-dimensional spaces and related problems, SIAM J. Comput., 11, 4, 721-736 (1982) · Zbl 0492.68050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.