cs.CG — Computational Geometry

Universal Support Theorems for Resilient Coverage

Contributed by Deep Bhattacharjee, Ushashi Bhattacharya, Sanjeevan Singha Roy

We prove that one finite set of points decides whether sensors cover a polygonal target under every failure rule in which an extra working sensor never hurts. The set is the same for every such rule, and on a face of dimension f the weakest point is fixed by f+1 sensors. The theorem holds in any dimension for functions that share a convex part and differ by affine terms. For sensing disks it gives the exact radius and power that keep the target covered under each rule, as rational numbers, the full trade-off between radius and budget, the smallest list of sensor groups whose loss breaks coverage, exact tests under independent placement errors, and protection plans proved optimal by a matching dual certificate.