TY - GEN
T1 - Computing best coverage path in the presence of obstacles in a sensor field
AU - Roy, Senjuti Basu
AU - Das, Gautam
AU - Das, Sajal
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=38149014043&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38149014043&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-73951-7_50
DO - 10.1007/978-3-540-73951-7_50
M3 - Conference contribution
AN - SCOPUS:38149014043
SN - 3540739483
SN - 9783540739487
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 577
EP - 588
BT - Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings
PB - Springer Verlag
T2 - 10th International Workshop on Algorithms and Data Structures, WADS 2007
Y2 - 15 August 2007 through 17 August 2007
ER -