{"id":{"repo_id":"utahstate","oai_identifier":"oai:digitalcommons.usu.edu:etd-9272"},"canonical_url":"https://search.ndltd.org/etd/utahstate/oai:digitalcommons.usu.edu:etd-9272","repository":{"repo_id":"utahstate","name":"Utah State University","base_url":"https://digitalcommons.usu.edu/do/oai/"},"display":{"title":"Algorithms for Covering Barrier Points by Mobile Sensors With Line Constraint","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Jain, Princy"],"institution":"Hosted by Utah State University Libraries","degree_name":"Master of Science (MS)","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Haitao Wang","Curtis Dyreson","Dan Watson"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T08:52:35Z","subjects":["barrier coverage","disk coverage","barrier points","mobile sensors","line constraint","computational geometry","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.26076/7088-7429"],"render_values":[{"text":"https://doi.org/10.26076/7088-7429","href":"https://doi.org/10.26076/7088-7429","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usu.edu/etd/8130","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usu.edu/etd/8130","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usu.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usu.edu%3Aetd-9272","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Haitao Wang","Curtis Dyreson","Dan Watson"]},{"key":"dc:creator","label":"Author","values":["Jain, Princy"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2010-01-01T08:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2021-08-01T07:00:00Z"]},{"key":"dc:publisher","label":"Institution","values":["Hosted by Utah State University Libraries"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["barrier coverage","disk coverage","barrier points","mobile sensors","line constraint","computational geometry","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usu.edu/etd/8130"]},{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.26076/7088-7429"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Algorithms for Covering Barrier Points by Mobile Sensors With Line Constraint"]}]}],"canonical_facts":{"dc:contributor":["Haitao Wang","Curtis Dyreson","Dan Watson"],"dc:creator":["Jain, Princy"],"dc:date.available":["2010-01-01T08:00:00Z"],"dc:date.created":["2021-08-01T07:00:00Z"],"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."],"dc:identifier":["https://digitalcommons.usu.edu/etd/8130"],"dc:identifier.doi":["https://doi.org/10.26076/7088-7429"],"dc:publisher":["Hosted by Utah State University Libraries"],"dc:subject":["barrier coverage","disk coverage","barrier points","mobile sensors","line constraint","computational geometry","Computer Sciences"],"dc:title":["Algorithms for Covering Barrier Points by Mobile Sensors With Line Constraint"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T08:52:35Z"}