Weak coverage of a rectangular barrier

Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Jan Maňnuch, Lata Narayanan, Jaroslav Opatrny, Sunil Shende, Ladislav Stacho

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. They are required to move to final locations so that they can detect any intruder crossing the region in a direction parallel to the sides of the rectangle, and thus provide weak bar-rier coverage of the region. We study three optimization problems related to the movement of sensors to achieve weak barrier coverage: minimizing the number of sensors moved (MinNum), minimizing the average distance moved by the sensors (MinSum), and minimizing the maximum distance moved by the sensors (MinMax). We give an O(n3/2) time algorithm for the MinNum problem for sensors of diameter 1 that are initially placed at integer positions; in contrast we show that the problem is NP-hard even for sensors of diameter 2 that are initially placed at integer posi-tions. We show that the MinSum problem is solvable in O(n log n) time for homogeneous range sensors in arbitrary initial positions for the Man-hattan metric, while it is NP-hard for heterogeneous sensor ranges for both Manhattan and Euclidean metrics. Finally, we prove that even very restricted homogeneous versions of the MinMax problem are NP-hard.

Original languageEnglish (US)
Title of host publicationAlgorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings
EditorsDimitris Fotakis, Aris Pagourtzis, Vangelis Th. Paschos
PublisherSpringer Verlag
Pages196-208
Number of pages13
ISBN (Print)9783319575858
DOIs
StatePublished - Jan 1 2017
Event10th International Conference on Algorithms and Complexity, CIAC 2017 - Athens, Greece
Duration: May 24 2017May 26 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10236 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th International Conference on Algorithms and Complexity, CIAC 2017
CountryGreece
CityAthens
Period5/24/175/26/17

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Weak coverage of a rectangular barrier'. Together they form a unique fingerprint.

  • Cite this

    Dobrev, S., Kranakis, E., Krizanc, D., Lafond, M., Maňnuch, J., Narayanan, L., Opatrny, J., Shende, S., & Stacho, L. (2017). Weak coverage of a rectangular barrier. In D. Fotakis, A. Pagourtzis, & V. T. Paschos (Eds.), Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings (pp. 196-208). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10236 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-57586-5_17