Computing best coverage path in the presence of obstacles in a sensor field

Senjuti Basu Roy, Gautam Das, Sajal Das

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

We study the presence of obstacles in computing BCP(s, t) (Best Coverage Path between two points s and t) in a 2D field under surveillance by sensors. Consider a set of m line segment obstacles and n point sensors on the plane. For any path between s to t, p is the least protected point along the path such that the Euclidean distance between p and its closest sensor is maximum. This distance (the path's cover value) is minimum for a BCP(s, t). We present two algorithmic results. For opaque obstacles, i.e., which obstruct paths and block sensing capabilities of sensors, computation of BCP(s, t) takes O((m 2n2 + n4)log(mn + n2)) time and O(m2n2 + n4) space. For transparent obstacles, i.e., which only obstruct paths, but allows sensing, computation of BCP(s, t) takes O(nm2 + n3) time and O(m2 + n 2) space. We believe, this is one of the first efforts to study the presence of obstacles in coverage problems in sensor networks.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings
PublisherSpringer Verlag
Pages577-588
Number of pages12
ISBN (Print)3540739483, 9783540739487
DOIs
StatePublished - 2007
Externally publishedYes
Event10th International Workshop on Algorithms and Data Structures, WADS 2007 - Halifax, Canada
Duration: Aug 15 2007Aug 17 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4619 LNCS

Other

Other10th International Workshop on Algorithms and Data Structures, WADS 2007
Country/TerritoryCanada
CityHalifax
Period8/15/078/17/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Computing best coverage path in the presence of obstacles in a sensor field'. Together they form a unique fingerprint.

Cite this