Abstract
We study the following problem: Given a set of points in the plane and a positive integer k > 0, construct a geometric strongly connected spanning digraph of out-degree at most k and whose longest edge length is the shortest possible. The motivation comes from the problem of replacing omnidirectional antennae in a sensor network with k directional antennae per sensor so that the resulting sensor network is strongly connected. The contribution of this is paper is twofold:
1) We introduce a notion of robustness of the radius in geometric graphs. This allows us to provide stronger lower bounds for the edge length needed to solve our problem, while nicely connecting two previously unrelated research directions (graph toughness and multiple directional antennae).
2) We present novel upper bound techniques which, in combination with stronger lower bounds, allow us to improve the previous approximation results for the edge length needed to achieve strong connectivity for k = 4 (from 2sin(π/5) to optimal) and k = 3 (from \(2\sin(\frac{\pi}{4})\) to \(2\sin(\frac{2\pi}{9})\)).
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
Bauer, D., Broersma, H., Schmeichel, E.: Toughness in graphs–a survey. Graphs and Combinatorics 22(1), 1–35 (2006)
Caragiannis, I., Kaklamanis, C., Kranakis, E., Krizanc, D., Wiese, A.: Communication in wireless networks with directional antennae. In: 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2008), Munich, Germany, June 14-16, pp. 344–351. IEEE/ACM (2008)
Dobrev, S., Kranakis, E., Krizanc, D., Opatrny, J., Ponce, O.M., Stacho, L.: Strong Connectivity in Sensor Networks with Given Number of Directional Antennae of Bounded Angle. In: Wu, W., Daescu, O. (eds.) COCOA 2010, Part II. LNCS, vol. 6509, pp. 72–86. Springer, Heidelberg (2010)
Francke, A., Hoffmann, M.: The euclidean degree-4 minimum spanning tree problem is np-hard. In: Proceedings of the 25th Annual Symposium on Computational Geometry, pp. 179–188. ACM (2009)
Kranakis, E., Krizanc, D., Morales, O.: Maintaining connectivity in sensor networks using directional antennae. In: Nikoletseas, S., Rolim, J. (eds.) Theoretical aspects of Distributed Computing in Sensor Networks, ch. 3, pp. 59–84. Springer (2010) ISBN 978-3-642-14848-4
Monma, C., Suri, S.: Transitions in geometric minimum spanning trees. Discrete and Computational Geometry 8(1), 265–293 (1992)
Papadimitriou, C.H.: The euclidean travelling salesman problem is np-complete. Theoretical Computer Science 4(3), 237–244 (1977)
Parker, R.G., Rardin, R.L.: Guaranteed performance heuristics for the bottleneck traveling salesman problem. Operations Research Letters 2(6), 269–272 (1984)
Toussaint, G.T.: The relative neighbourhood graph of a finite planar set. Pattern Recognition 12(4), 261–268 (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dobrev, S., Kranakis, E., Ponce, O.M., Plžík, M. (2012). Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGs. In: Hirsch, E.A., Karhumäki, J., Lepistö, A., Prilutskii, M. (eds) Computer Science – Theory and Applications. CSR 2012. Lecture Notes in Computer Science, vol 7353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30642-6_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-30642-6_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30641-9
Online ISBN: 978-3-642-30642-6
eBook Packages: Computer ScienceComputer Science (R0)