Back to search

Hosted by Utah State University Libraries

Algorithms for Covering Barrier Points by Mobile Sensors With Line Constraint

Abstract

dc:description.abstract

In this thesis, we develop efficient algorithms for the problem of covering barrier points by mobile sensors. Each sensor is represented by a point in the plane with the same covering range r so that any point within distance r from the sensor can be covered by the sensor. Given a set B of m points (called “barrier points”) and a set S of n points (representing the “sensors”) in the plane, the problem is to move the sensors so that each barrier point is covered by at least one sensor and the maximum movement of all sensors is minimized. The problem is NP-hard. In this thesis, we consider two line-constrained variations of the problem and present efficient algorithms that improve the previous work. In the first problem, all sensors are given on a line ℓ and are required to move on ℓ only while the barrier points can be anywhere in the plane. We propose an O((n + m) log(n + m)) time algorithm for the problem. We also consider the weighted case where each sensor has a weight; we give an O((m + n) log2(m + n)) time algorithm for this case. In the second problem, all barrier points are on ℓ while all sensors are in the plane but are required to move to ℓ to cover all barrier points. We solve the weighted case in O(m log m + n log2 n) time.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
Hosted by Utah State University Libraries

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Jain, Princy
Contributors dc:contributor
  • Haitao Wang
  • Curtis Dyreson
  • Dan Watson

Subjects

dc:subject × 7

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Utah State University
Base URL
digitalcommons.usu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Jain, Princy. Algorithms for Covering Barrier Points by Mobile Sensors With Line Constraint. Thesis thesis, Hosted by Utah State University Libraries, https://digitalcommons.usu.edu/etd/8130