Abstract
In the barrier resilience problem (introduced by Kumar et al., Wireless Networks 2007), we are given a collection of regions of the plane, acting as obstacles, and we would like to remove the minimum number of regions so that two fixed points can be connected without crossing any region. In this paper, we show that the problem is NP-hard when the regions are arbitrarily fat regions (even when they are axis-aligned rectangles of aspect ratio \(1 : (1 + \varepsilon )\)). We also show that the problem is fixed-parameter tractable (FPT) for such regions. Using our FPT algorithm, we show that if the regions are \(\beta \)-fat and their arrangement has bounded ply \(\varDelta \), there is a \((1+\varepsilon )\)-approximation that runs in \(O(2^{f(\varDelta , \varepsilon ,\beta )}n^7)\) time, where \(f\in O(\frac{\varDelta ^2\beta ^6}{\varepsilon ^4}\log (\beta \varDelta /\varepsilon ))\).
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
Similar content being viewed by others
Notes
- 1.
Note that no other option is possible under our general position assumption.
- 2.
Note that the well-separatedness of \(p\) and \(q\) is used to prove a factor 2 instead of 3. Everything still works for ill-separated points, at a slight increase of the constants. Our most general statements for \(\beta \)-fat regions do not make this requirement.
- 3.
In fact, we could choose any disjoint collection such that after their removal there are no more segments of this type longer than \(\lambda \).
- 4.
A similar fact was also observed in [16].
References
Alt, H., Cabello, S., Giannopoulos, P., Knauer, C.: On some connection problems in straight-line segment arrangements. In: Proceedings of the EuroCG, pp. 27–30 (2011)
Bereg, S., Kirkpatrick, D.: Approximating barrier resilience in wireless sensor networks. In: Dolev, S. (ed.) ALGOSENSORS 2009. LNCS, vol. 5804, pp. 29–40. Springer, Heidelberg (2009)
Chang, C.-Y.: The k-barrier coverage mechanism in wireless visual sensor networks. In: Proceedings of the WCNC, pp. 2318–2322 (2012)
Chen, D.Z., Gu, Y., Li, J., Wang, H.: Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 177–188. Springer, Heidelberg (2012). http://arxiv.org/abs/1207.6409
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008)
de Berg, M., Katz, M.J., van der Stappen, A.F., Vleugels, J.: Realistic input models for geometric algorithms. In: Proceedings of the SoCG, pp. 294–303 (1997)
Gibson, M., Kanade, G., Varadarajan, K.: On isolating points using disks. In: Demetrescu, C., Halldórsson, M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 61–69. Springer, Heidelberg (2011)
He, S., Chen, J., Li, X., Shen, X., Sun, Y.: Cost-effective barrier coverage by mobile sensor networks. In: Proceedings of the INFOCOM, pp. 819–827 (2012)
Hu, T.C.: Multi-commodity network flows. Oper. Res. 11(3), 344–360 (1963)
Korman, M., Löffler, M., Silveira, R.I., Strash, D.: On the complexity of barrier resilience for fat regions. CoRR, abs/1302.4707 (2013)
Kumar, S., Lai, T.-H., Arora, A.: Barrier coverage with wireless sensors. In: Proceedings of the MOBICOM, pp. 284–298 (2005)
Kumar, S., Lai, T.-H., Arora, A.: Barrier coverage with wireless sensors. Wirel. Netw. 13(6), 817–834 (2007)
Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394–406 (2006)
Miller, G., Teng, S., Thurston, W., Vavasis, S.: Separators for sphere-packings and nearest neighbor graphs. J. ACM 44(1), 1–29 (1992)
Tseng, K.-C.R.: Resilience of wireless sensor networks. Master’s thesis, University of British Columbia (2011)
Tseng, K.-C.R., Kirkpatrick, D.: On barrier resilience of sensor networks. In: Erlebach, T., Nikoletseas, S., Orponen, P. (eds.) ALGOSENSORS 2011. LNCS, vol. 7111, pp. 130–144. Springer, Heidelberg (2012)
Xiao, M.: Simple and improved parameterized algorithms for multiterminal cuts. Theor. Comput. Syst. 46(4), 723–736 (2010)
Acknowledgements
M.K was partially supported by the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia and the European Union. M.L. was supported by the Netherlands Organisation for Scientific Research (NWO) under grant 639.021.123. R.S. was partially supported by FP7 Marie Curie Actions Individual Fellowship PIEF-GA-2009-251235 and by FCT through grant SFRH/BPD/88455/2012. M.K and R.S. were also supported by projects MINECO MTM2012-30951 and Gen. Cat. DGR2009SGR1040 and by ESF EUROCORES program EuroGIGA-ComPoSe IP04-MICINN project EUI-EURC-2011-4306.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Korman, M., Löffler, M., Silveira, R.I., Strash, D. (2014). On the Complexity of Barrier Resilience for Fat Regions. In: Flocchini, P., Gao, J., Kranakis, E., Meyer auf der Heide, F. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2013. Lecture Notes in Computer Science(), vol 8243. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45346-5_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-45346-5_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45345-8
Online ISBN: 978-3-642-45346-5
eBook Packages: Computer ScienceComputer Science (R0)