{"id":{"repo_id":"utahstate","oai_identifier":"oai:digitalcommons.usu.edu:etd-4918"},"canonical_url":"https://search.ndltd.org/etd/utahstate/oai:digitalcommons.usu.edu:etd-4918","repository":{"repo_id":"utahstate","name":"Utah State University","base_url":"https://digitalcommons.usu.edu/do/oai/"},"display":{"title":"Minimizing Aggregate Movements for Interval Coverage","abstract":"We present an efficient algorithm for solving an interval coverage problem. Given n intervals of the same length on a line L and a line segment B on L, we want to move the intervals along L such that every point of B is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a fundamental computational geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work gave an O(n2) time algorithm for it. In this thesis, by discovering many interesting observations and developing new algorithmic techniques, we present an O(n log n) time algorithm for this problem. We also show that Ω(n log n) is the lower bound for the time complexity. Therefore, our algorithm is optimal. Further, our observations and algorithmic techniques may be useful for solving other related problems.","abstract_html":"We present an efficient algorithm for solving an interval coverage problem. Given n intervals of the same length on a line L and a line segment B on L, we want to move the intervals along L such that every point of B is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a fundamental computational geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work gave an O(n2) time algorithm for it. In this thesis, by discovering many interesting observations and developing new algorithmic techniques, we present an O(n log n) time algorithm for this problem. We also show that Ω(n log n) is the lower bound for the time complexity. Therefore, our algorithm is optimal. Further, our observations and algorithmic techniques may be useful for solving other related problems.","abstract_has_math":false,"creators":["Andrews, Aaron M."],"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","Minghui Jiang","Vladimir Kulyukin"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T08:48:19Z","subjects":["Minimizing Aggregate Movements","Interval Coverage","Aggregate Movements","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.26076/f34e-f3aa"],"render_values":[{"text":"https://doi.org/10.26076/f34e-f3aa","href":"https://doi.org/10.26076/f34e-f3aa","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usu.edu/etd/3893","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usu.edu/etd/3893","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-4918","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Haitao Wang","Minghui Jiang","Vladimir Kulyukin"]},{"key":"dc:creator","label":"Author","values":["Andrews, Aaron M."]}]},{"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":["2014-05-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":["Minimizing Aggregate Movements","Interval Coverage","Aggregate Movements","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usu.edu/etd/3893"]},{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.26076/f34e-f3aa"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["We present an efficient algorithm for solving an interval coverage problem. Given n intervals of the same length on a line L and a line segment B on L, we want to move the intervals along L such that every point of B is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a fundamental computational geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work gave an O(n2) time algorithm for it. In this thesis, by discovering many interesting observations and developing new algorithmic techniques, we present an O(n log n) time algorithm for this problem. We also show that Ω(n log n) is the lower bound for the time complexity. Therefore, our algorithm is optimal. Further, our observations and algorithmic techniques may be useful for solving other related problems."]},{"key":"dc:title","label":"Title","values":["Minimizing Aggregate Movements for Interval Coverage"]}]}],"canonical_facts":{"dc:contributor":["Haitao Wang","Minghui Jiang","Vladimir Kulyukin"],"dc:creator":["Andrews, Aaron M."],"dc:date.available":["2010-01-01T08:00:00Z"],"dc:date.created":["2014-05-01T07:00:00Z"],"dc:description.abstract":["We present an efficient algorithm for solving an interval coverage problem. Given n intervals of the same length on a line L and a line segment B on L, we want to move the intervals along L such that every point of B is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a fundamental computational geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work gave an O(n2) time algorithm for it. In this thesis, by discovering many interesting observations and developing new algorithmic techniques, we present an O(n log n) time algorithm for this problem. We also show that Ω(n log n) is the lower bound for the time complexity. Therefore, our algorithm is optimal. Further, our observations and algorithmic techniques may be useful for solving other related problems."],"dc:identifier":["https://digitalcommons.usu.edu/etd/3893"],"dc:identifier.doi":["https://doi.org/10.26076/f34e-f3aa"],"dc:publisher":["Hosted by Utah State University Libraries"],"dc:subject":["Minimizing Aggregate Movements","Interval Coverage","Aggregate Movements","Computer Sciences"],"dc:title":["Minimizing Aggregate Movements for Interval Coverage"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T08:48:19Z"}