On the barrier-resilience of arrangements of ray-sensors

Abstract

Given an arrangement A of n sensors and two points s and t in the plane, the barrier resilience of A with respect to s and t is the minimum number of sensors whose removal permits a path from s to t such that the path does not intersect the coverage region of any sensor in A. When the surveillance domain is the entire plane and sensor coverage regions are unit line segments, even with restricted orientations, the problem of determining the barrier resilience is known to be NP-hard. On the other hand, if sensor coverage regions are arbitrary lines, the problem has a trivial linear time solution. In this paper, we give an O(n2m) time algorithm for computing the barrier resilience when each sensor coverage region is an arbitrary ray, where m is the number of sensor intersections.