Abstract
We give a new local test, called a Half-Space Proximal or HSP test, for extracting a sparse directed or undirected subgraph of a given unit disk graph. The HSP neighbors of each vertex are unique, given a fixed underlying unit disk graph. The HSP test is a fully distributed, computationally simple algorithm that is applied independently to each vertex of a unit disk graph. The directed spanner obtained by this test is shown to be strongly connected, has out-degree at most six, its dilation is at most 2π+1, contains the minimum weight spanning tree as its subgraph and, unlike the Yao graph, it is rotation invariant. Since no coordinate assumption is needed to determine the HSP nodes, the test can be applied in any metric space.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pp. 489–498 (1995)
Barriere, L., Fraignaud, P., Narayanan, L., Opatrny, J.: Robust position-based routing in wireless ad hoc networks with unstable transmission ranges. In: The Proceedings of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pp. 19–27 (2001)
Boone, P., Chavez, E., Gleitzky, L., Kranakis, E., Opatrny, J., Salazar, G., Urrutia, J.: Morelia Test: Improving the Efficiency of the Gabriel Test and Face Routing in Ad-hoc Networks. In: Kralovic, R., Sýkora, O. (eds.) SIROCCO 2004. LNCS, vol. 3104, pp. 23–34. Springer, Heidelberg (2004)
Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. In: The Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pp. 48–55 (1999)
Broch, J., Maltz, D., Johnson, D., Hu, Y.-C., Jetcheva, J.: A performance comparison of multi-hop wireless ad hoc network routing protocols. In: Mobile Computing and Networking, pp. 85–97 (1998)
Datta, S., Stojmenovic, I., Wu, J.: Internal node and shortcut based routing with guaranteed delivery in wireless networks. In: Proc. IEEE Int. Conf. on Distributed Computing and Systems Workshops; Cluster Computing, pp. 461–466 (2001)
Gabriel, K., Sokal, R.: A new statistical approach to geographic variation analysis. Systematic Zoology 18, 259–278 (1969)
Gao, J., Guibas, L., Hershberger, J., Zhang, L., Zhu, A.: Geometric Spanner for Routing in Mobile Networks. In: Proceedings of the 2nd ACM International Symposium on Mobile Ad hoc Networking and Computing, pp. 45–55 (2001)
Jaromczyk, J.W., Toussaint, G.T.: Relative neighborhood graphs and their relatives. Proc. IEEE 80(9), 1502–1517 (1992)
Keil, J.M., Gutwin, C.A.: Classes of Graphs which approximate the complete euclidean graph. Discrete Comp. Geom. 7, 13–28 (1992)
Kranakis, E., Singh, H., Urrutia, J.: Compass Routing on Geometric Networks. In: Proceedings of 11th Canadian Conference on Computational Geometry, Vancouver, pp. 51–54 (August 1999)
Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically Optimal Geometric Mobile Ad-Hoc Routing. In: Proc. of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pp. 24–33 (2002)
Li, X.-Y., Wan, P.-J., Wang, Y., Frieder, O.: Sparse Power Efficient Topology for Wireless Networks. In: HICSS 2002: Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS 2002), vol. 9, p. 296.2 (2002)
Li, X., Wang, Y.: Efficient construction of low weight bounded degree planar spanner. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697. Springer, Heidelberg (2003)
Li, X.-Y., Calinescu, G., Wan, P.-J.: Localized Delaunay Triangulation with Application in Ad Hoc Wireless Networks, Distributed construction of planar spanner and routing for ad hoc wireless networks. In: IEEE INFOCOM (2002)
Perkins, C.E. (ed.): Ad Hoc Networking. Addison-Wesley, Reading (2001)
Toussaint, G.: The relative neighbourhood graph of a finite planar set. Pattern Recognition 12(4), 261–268 (1980)
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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chavez, E. et al. (2006). Half-Space Proximal: A New Local Test for Extracting a Bounded Dilation Spanner of a Unit Disk Graph. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds) Principles of Distributed Systems. OPODIS 2005. Lecture Notes in Computer Science, vol 3974. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11795490_19
Download citation
DOI: https://doi.org/10.1007/11795490_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36321-7
Online ISBN: 978-3-540-36322-4
eBook Packages: Computer ScienceComputer Science (R0)