### 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(n^{3}^{/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 language | English (US) |
---|---|

Title of host publication | Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings |

Editors | Dimitris Fotakis, Aris Pagourtzis, Vangelis Th. Paschos |

Publisher | Springer Verlag |

Pages | 196-208 |

Number of pages | 13 |

ISBN (Print) | 9783319575858 |

DOIs | |

State | Published - Jan 1 2017 |

Event | 10th International Conference on Algorithms and Complexity, CIAC 2017 - Athens, Greece Duration: May 24 2017 → May 26 2017 |

### Publication series

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

Volume | 10236 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 10th International Conference on Algorithms and Complexity, CIAC 2017 |
---|---|

Country | Greece |

City | Athens |

Period | 5/24/17 → 5/26/17 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*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

}

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 -