Complexity of barrier coverage with relocatable sensors in the plane

Stefan Dobrev, Stephane Durocher, Mohsen Eftekhari, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Sunil Shende, Jorge Urrutia

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

11 Citations (Scopus)

Abstract

We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in the plane and they can relocate to the barriers. We assume that each sensor can detect any intruder in a circular area centered at the sensor. Given a set of barriers and a set of sensors located in the plane, we study three problems: the feasibility of barrier coverage, the problem of minimizing the largest relocation distance of a sensor (MinMax), and the problem of minimizing the sum of relocation distances of sensors (MinSum). When sensors are permitted to move to arbitrary positions on the barrier, the problems are shown to be NP-complete. We also study the case when sensors use perpendicular movement to one of the barriers. We show that when the barriers are parallel, both the MinMax and MinSum problems can be solved in polynomial time. In contrast, we show that even the feasibility problem is NP-complete if two perpendicular barriers are to be covered, even if the sensors are located at integer positions, and have only two possible sensing ranges. On the other hand, we give an O(n3/2) algorithm for a natural special case of this last problem.

Original languageEnglish (US)
Title of host publicationAlgorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings
Pages170-182
Number of pages13
DOIs
StatePublished - Sep 9 2013
Event8th International Conference on Algorithms and Complexity, CIAC 2013 - Barcelona, Spain
Duration: May 22 2013May 24 2013

Publication series

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

Other

Other8th International Conference on Algorithms and Complexity, CIAC 2013
CountrySpain
CityBarcelona
Period5/22/135/24/13

Fingerprint

Coverage
Sensor
Sensors
Relocation
Min-max
Perpendicular
NP-complete problem
Line segment
Computational complexity
Polynomial time
Sensing
Covering
Polynomials
Integer
Arbitrary
Range of data

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Dobrev, S., Durocher, S., Eftekhari, M., Georgiou, K., Kranakis, E., Krizanc, D., ... Urrutia, J. (2013). Complexity of barrier coverage with relocatable sensors in the plane. In Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings (pp. 170-182). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7878 LNCS). https://doi.org/10.1007/978-3-642-38233-8_15
Dobrev, Stefan ; Durocher, Stephane ; Eftekhari, Mohsen ; Georgiou, Konstantinos ; Kranakis, Evangelos ; Krizanc, Danny ; Narayanan, Lata ; Opatrny, Jaroslav ; Shende, Sunil ; Urrutia, Jorge. / Complexity of barrier coverage with relocatable sensors in the plane. Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. 2013. pp. 170-182 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{18fbefdf8563406bb20c3425ac68799c,
title = "Complexity of barrier coverage with relocatable sensors in the plane",
abstract = "We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in the plane and they can relocate to the barriers. We assume that each sensor can detect any intruder in a circular area centered at the sensor. Given a set of barriers and a set of sensors located in the plane, we study three problems: the feasibility of barrier coverage, the problem of minimizing the largest relocation distance of a sensor (MinMax), and the problem of minimizing the sum of relocation distances of sensors (MinSum). When sensors are permitted to move to arbitrary positions on the barrier, the problems are shown to be NP-complete. We also study the case when sensors use perpendicular movement to one of the barriers. We show that when the barriers are parallel, both the MinMax and MinSum problems can be solved in polynomial time. In contrast, we show that even the feasibility problem is NP-complete if two perpendicular barriers are to be covered, even if the sensors are located at integer positions, and have only two possible sensing ranges. On the other hand, we give an O(n3/2) algorithm for a natural special case of this last problem.",
author = "Stefan Dobrev and Stephane Durocher and Mohsen Eftekhari and Konstantinos Georgiou and Evangelos Kranakis and Danny Krizanc and Lata Narayanan and Jaroslav Opatrny and Sunil Shende and Jorge Urrutia",
year = "2013",
month = "9",
day = "9",
doi = "10.1007/978-3-642-38233-8_15",
language = "English (US)",
isbn = "9783642382321",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "170--182",
booktitle = "Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings",

}

Dobrev, S, Durocher, S, Eftekhari, M, Georgiou, K, Kranakis, E, Krizanc, D, Narayanan, L, Opatrny, J, Shende, S & Urrutia, J 2013, Complexity of barrier coverage with relocatable sensors in the plane. in Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7878 LNCS, pp. 170-182, 8th International Conference on Algorithms and Complexity, CIAC 2013, Barcelona, Spain, 5/22/13. https://doi.org/10.1007/978-3-642-38233-8_15

Complexity of barrier coverage with relocatable sensors in the plane. / Dobrev, Stefan; Durocher, Stephane; Eftekhari, Mohsen; Georgiou, Konstantinos; Kranakis, Evangelos; Krizanc, Danny; Narayanan, Lata; Opatrny, Jaroslav; Shende, Sunil; Urrutia, Jorge.

Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. 2013. p. 170-182 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7878 LNCS).

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

TY - GEN

T1 - Complexity of barrier coverage with relocatable sensors in the plane

AU - Dobrev, Stefan

AU - Durocher, Stephane

AU - Eftekhari, Mohsen

AU - Georgiou, Konstantinos

AU - Kranakis, Evangelos

AU - Krizanc, Danny

AU - Narayanan, Lata

AU - Opatrny, Jaroslav

AU - Shende, Sunil

AU - Urrutia, Jorge

PY - 2013/9/9

Y1 - 2013/9/9

N2 - We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in the plane and they can relocate to the barriers. We assume that each sensor can detect any intruder in a circular area centered at the sensor. Given a set of barriers and a set of sensors located in the plane, we study three problems: the feasibility of barrier coverage, the problem of minimizing the largest relocation distance of a sensor (MinMax), and the problem of minimizing the sum of relocation distances of sensors (MinSum). When sensors are permitted to move to arbitrary positions on the barrier, the problems are shown to be NP-complete. We also study the case when sensors use perpendicular movement to one of the barriers. We show that when the barriers are parallel, both the MinMax and MinSum problems can be solved in polynomial time. In contrast, we show that even the feasibility problem is NP-complete if two perpendicular barriers are to be covered, even if the sensors are located at integer positions, and have only two possible sensing ranges. On the other hand, we give an O(n3/2) algorithm for a natural special case of this last problem.

AB - We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in the plane and they can relocate to the barriers. We assume that each sensor can detect any intruder in a circular area centered at the sensor. Given a set of barriers and a set of sensors located in the plane, we study three problems: the feasibility of barrier coverage, the problem of minimizing the largest relocation distance of a sensor (MinMax), and the problem of minimizing the sum of relocation distances of sensors (MinSum). When sensors are permitted to move to arbitrary positions on the barrier, the problems are shown to be NP-complete. We also study the case when sensors use perpendicular movement to one of the barriers. We show that when the barriers are parallel, both the MinMax and MinSum problems can be solved in polynomial time. In contrast, we show that even the feasibility problem is NP-complete if two perpendicular barriers are to be covered, even if the sensors are located at integer positions, and have only two possible sensing ranges. On the other hand, we give an O(n3/2) algorithm for a natural special case of this last problem.

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

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

U2 - 10.1007/978-3-642-38233-8_15

DO - 10.1007/978-3-642-38233-8_15

M3 - Conference contribution

AN - SCOPUS:84883385926

SN - 9783642382321

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

SP - 170

EP - 182

BT - Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings

ER -

Dobrev S, Durocher S, Eftekhari M, Georgiou K, Kranakis E, Krizanc D et al. Complexity of barrier coverage with relocatable sensors in the plane. In Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. 2013. p. 170-182. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-38233-8_15