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
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th International Workshop on Algorithms and Data Structures, WADS 2007
CountryCanada
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