Barrier resilience

In this problem, the region under surveillance from each sensor is modeled as a unit disk in the Euclidean plane.

Another variation of the problem counts the number of times a path crosses the boundary of a sensor disk.

[2] The corresponding problem for barriers of some other shapes, including unit-length line segments or axis-aligned rectangles of aspect ratio close to 1, is known to be NP-hard.

[3] A variation of the barrier resilience problem, studied by Kumar, Lai & Arora (2005), restricts both the sensors and the escape path to a rectangle in the plane.

For unit disks with bounded ply (the maximum number of disks that have a common intersection) there exists a polynomial-time approximation scheme for the resilience, that can be generalized to barrier shapes of the same size as each other with bounded aspect ratios.

Barrier resilience. This instance has resilience = 1 (it is possible to connect the green regions by a path that crosses only one barrier, the blue one) but the barrier must be crossed twice by the path.