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 Citations (Scopus)

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

Fingerprint

Coverage
Sensor
Sensors
NP-complete problem
Computational complexity
Min-max Problem
Metric
Average Distance
Integer
Min-max
Rectangle
Range of data
Euclidean
Optimization Problem
Arbitrary

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Dobrev, S., Kranakis, E., Krizanc, D., Lafond, M., Maňnuch, J., Narayanan, L., ... 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
Dobrev, Stefan ; Kranakis, Evangelos ; Krizanc, Danny ; Lafond, Manuel ; Maňnuch, Jan ; Narayanan, Lata ; Opatrny, Jaroslav ; Shende, Sunil ; Stacho, Ladislav. / Weak coverage of a rectangular barrier. Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings. editor / Dimitris Fotakis ; Aris Pagourtzis ; Vangelis Th. Paschos. Springer Verlag, 2017. pp. 196-208 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{31614821ff39465b86cef393262c721c,
title = "Weak coverage of a rectangular barrier",
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.",
author = "Stefan Dobrev and Evangelos Kranakis and Danny Krizanc and Manuel Lafond and Jan Maňnuch and Lata Narayanan and Jaroslav Opatrny and Sunil Shende and Ladislav Stacho",
year = "2017",
month = "1",
day = "1",
doi = "10.1007/978-3-319-57586-5_17",
language = "English (US)",
isbn = "9783319575858",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "196--208",
editor = "Dimitris Fotakis and Aris Pagourtzis and Paschos, {Vangelis Th.}",
booktitle = "Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings",
address = "Germany",

}

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 & VT Paschos (eds), Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10236 LNCS, Springer Verlag, pp. 196-208, 10th International Conference on Algorithms and Complexity, CIAC 2017, Athens, Greece, 5/24/17. https://doi.org/10.1007/978-3-319-57586-5_17

Weak coverage of a rectangular barrier. / Dobrev, Stefan; Kranakis, Evangelos; Krizanc, Danny; Lafond, Manuel; Maňnuch, Jan; Narayanan, Lata; Opatrny, Jaroslav; Shende, Sunil; Stacho, Ladislav.

Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings. ed. / Dimitris Fotakis; Aris Pagourtzis; Vangelis Th. Paschos. Springer Verlag, 2017. p. 196-208 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10236 LNCS).

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

TY - GEN

T1 - Weak coverage of a rectangular barrier

AU - Dobrev, Stefan

AU - Kranakis, Evangelos

AU - Krizanc, Danny

AU - Lafond, Manuel

AU - Maňnuch, Jan

AU - Narayanan, Lata

AU - Opatrny, Jaroslav

AU - Shende, Sunil

AU - Stacho, Ladislav

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85018448074&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85018448074&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-57586-5_17

DO - 10.1007/978-3-319-57586-5_17

M3 - Conference contribution

AN - SCOPUS:85018448074

SN - 9783319575858

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 196

EP - 208

BT - Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings

A2 - Fotakis, Dimitris

A2 - Pagourtzis, Aris

A2 - Paschos, Vangelis Th.

PB - Springer Verlag

ER -

Dobrev S, Kranakis E, Krizanc D, Lafond M, Maňnuch J, Narayanan L et al. Weak coverage of a rectangular barrier. In Fotakis D, Pagourtzis A, Paschos VT, editors, Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings. Springer Verlag. 2017. p. 196-208. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-57586-5_17