### 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(n^{3/2}) algorithm for a natural special case of this last problem.

Original language | English (US) |
---|---|

Title of host publication | Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings |

Pages | 170-182 |

Number of pages | 13 |

DOIs | |

Publication status | Published - Sep 9 2013 |

Event | 8th International Conference on Algorithms and Complexity, CIAC 2013 - Barcelona, Spain Duration: May 22 2013 → May 24 2013 |

### Publication series

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

Volume | 7878 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 8th International Conference on Algorithms and Complexity, CIAC 2013 |
---|---|

Country | Spain |

City | Barcelona |

Period | 5/22/13 → 5/24/13 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*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