A POLYNOMIAL-TIME ALGORITHM FOR COMPUTING THE RESILIENCE OF ARRANGEMENTS OF RAY SENSORS
David G. Kirkpatrick, Boting Yang, Sandra Zilles · International Journal of Computational Geometry & Applications · 2014
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 study the case where each sensor coverage region is an arbitrary ray, and give an O(n2m) time algorithm for computing the barrier resilience when there are m ⩾ 1 sensor intersections.