Approximating Barrier Resilience for Arrangements of Non-identical Disk Sensors

摘要

Let A be an arrangement of n sensors constituting a barrier between two regions S and T. The resilience of A with respect to S and T, denoted ρ(A, S, T), is defined as the number of sensors in A that must be removed in order for there to be an S - T path that is not detected by any sensor. We introduce the Multi-Path Algorithm (MPA) and show that it guarantees a 2-approximation of ρ(A, S, T) in time polynomial in n when sensors are unit disks in a two dimensional plane; this tightens to a 1.5-approximation when S and T are moderately well-separated. We also define a generalization of ρ(A, S, T) denoted ρ_c(A, S, T), which is the resilience of the barrier if regions covered by more than c distinct sensors in the original arrangement are treated as inaccessible. Then when the unit size constraint is relaxed, we prove that the MPA can still guarantee a 2-approximation of ρ_c(A, S, T) for any constant c in time polynomial in n for arrangements of approximately equal-sized sensors.