Abstract
In this paper, we consider the problems for covering multiple intervals on a line. Given a set B of m line segments (called “barriers”) on a horizontal line L and another set S of n horizontal line segments of the same length in the plane, we want to move all segments of S to L so that their union covers all barriers and the maximum movement of all segments of S is minimized. Previously, an \(O(n^3\log n)\)-time algorithm was given for the problem but only for the special case \(m=1\). In this paper, we propose an \(O(n^2\log n\log \log n+nm\log m)\)-time algorithm for any m, which improves the previous work even for \(m=1\). We then consider a line-constrained version of the problem in which the segments of S are all initially on the line L. Previously, an \(O(n\log n)\)-time algorithm was known for the case \(m=1\). We present an algorithm of \(O((n+m)\log (n+ m))\) time for any m. These problems may have applications in mobile sensor barrier coverage in wireless sensor networks.
This research was supported in part by NSF under Grant CCF-1317143.
Access provided by CONRICYT-eBooks. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Andrews, A., Wang, H.: Minimizing the aggregate movements for interval coverage. Algorithmica 78, 47–85 (2017)
Bhattacharya, B., Burmester, B., Hu, Y., Kranakis, E., Shi, Q., Wiese, A.: Optimal movement of mobile sensors for barrier coverage of a planar region. Theoretical Computer Science 410(52), 5515–5528 (2009)
Chen, D., Gu, Y., Li, J., Wang, H.: Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain. Discrete and Computational Geometry 50, 374–408 (2013)
Chen, D., Tan, X., Wang, H., Wu, G.: Optimal point movement for covering circular regions. Algorithmica 72, 379–399 (2013)
Czyzowicz, J., et al.: On minimizing the maximum sensor movement for barrier coverage of a line segment. In: Ruiz, P.M., Garcia-Luna-Aceves, J.J. (eds.) ADHOC-NOW 2009. LNCS, vol. 5793, pp. 194–212. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04383-3_15
Czyzowicz, J., et al.: On minimizing the sum of sensor movements for barrier coverage of a line segment. In: Nikolaidis, I., Wu, K. (eds.) ADHOC-NOW 2010. LNCS, vol. 6288, pp. 29–42. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14785-2_3
Dobrev, S., Durocher, S., Eftekhari, M., Georgiou, K., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S., Urrutia, J.: Complexity of barrier coverage with relocatable sensors in the plane. Theoretical Computer Science 579, 64–73 (2015)
Frederickson, G., Johnson, D.: Generalized selection and ranking: Sorted matrices. SIAM Journal on Computing 13(1), 14–30 (1984)
Kumar, S., Lai, T., Arora, A.: Barrier coverage with wireless sensors. In: Proc. of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom), pp. 284–298 (2005)
Li, S., Shen, H.: Minimizing the maximum sensor movement for barrier coverage in the plane. In: Proc. of the 2015 IEEE Conference on Computer Communications (INFOCOM), pp. 244–252 (2015)
Li, S., Wang, H.: Algorithms for covering multiple barriers. arXiv:1704.06870 (2017)
Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM 30(4), 852–865 (1983)
Mehrandish, M.: On Routing, Backbone Formation and Barrier Coverage in Wireless Ad Doc and Sensor Networks. Ph.D. thesis, Concordia University, Montreal, Quebec, Canada (2011)
Mehrandish, M., Narayanan, L., Opatrny, J.: Minimizing the number of sensors moved on line barriers. In: Proc. of IEEE Wireless Communications and Networking Conference (WCNC), pp. 653–658 (2011)
Wang, H., Zhang, X.: Minimizing the maximum moving cost of interval coverage. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 188–198. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48971-0_17. Full version to appear in International Journal of Computational Geometry and Application (IJCGA)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Li, S., Wang, H. (2017). Algorithms for Covering Multiple Barriers. In: Ellen, F., Kolokolova, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2017. Lecture Notes in Computer Science(), vol 10389. Springer, Cham. https://doi.org/10.1007/978-3-319-62127-2_45
Download citation
DOI: https://doi.org/10.1007/978-3-319-62127-2_45
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62126-5
Online ISBN: 978-3-319-62127-2
eBook Packages: Computer ScienceComputer Science (R0)