Algorithms for computing Best Coverage Path in the presence of obstacles in a sensor field

Senjuti Basu Roy, Gautam Das, Sajal K. Das

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We compute BCP(s,t), a Best Coverage Path between two points s and t in the presence of m line segment obstacles in a 2D field under surveillance by n sensors. Based on nature of obstacles, we have studied two variants of the problem. For opaque obstacles, which obstruct paths and block sensing capabilities of sensors, we present algorithm ExOpaque for computation of BCP(s,t) that takes O(( m2n2+ n4)log(mn+ n2)) time and O( m2n2+ n4) space. For transparent obstacles, which only obstruct paths but allow sensing, we present an exact as well as an approximation algorithm, where the exact algorithm ExTransparent takes O(n( m+n)2(logn+log(m+n))) time and O(n( m+n)2) space. On the other hand, the approximation algorithm ApproxTransparent takes O(n(m+n)(logn+log(m+n))) time and O(n(m+n)) space with an approximation factor of O(k), using k-spanners of visibility graph.

Original languageEnglish (US)
Pages (from-to)86-97
Number of pages12
JournalJournal of Discrete Algorithms
StatePublished - May 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Coverage problem
  • Sensor network
  • Spanner
  • Visibility graph
  • Voronoi diagram


Dive into the research topics of 'Algorithms for computing Best Coverage Path in the presence of obstacles in a sensor field'. Together they form a unique fingerprint.

Cite this