Suppose that the whole plane (or a large region) is monitored by a set S of stationary sensors such that each element s ∈ S can observe an axis-parallel unit square R(s) centered at s, which is called the range of s. Each sensor s is equipped with a battery of unit lifetime. Is it true that if every point of the plane belongs to the range of many sensors, then we can monitor the plane for a long time without running out of power? If S can be partitioned into k parts S1, S2, . . . , S k such that, for each i, the sensors in Si together can observe the whole plane, then the plane can be monitored with no interruption for k units of time. Indeed, we can first switch on all sensors belonging to S1. After these sensors run out of battery, we can switch on all elements of S2, etc. We arrive at the following problem. Let m(k) denote the smallest positive integer m such that any m-fold covering of the plane with axis-parallel unit squares splits into at least k coverings. We show that m(k) = O(k 2 ), and generalize this result to translates of any centrally symmetric convex polygon in the place of squares. From the other direction, we know only that m(k) ≥ 4k/3 − 1.
Pach and Tóth REF showed that a t-fold cover of translates of a centrally-symmetric open convex polygon can be decomposed into ( √ t) covers.
Decomposition of multiple coverings into many parts
SCG '07
Mathematics Computer Science