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

We compute BCP(s,t)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)BCP(s,t) that takes O((m2n2+n4)log(mn+n2))O((m2n2+n4)log(mn+n2)) time and O(m2n2+n4)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)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))O(n(m+n)) space with an approximation factor of O(k)O(k), using k-spanners of visibility graph.