Paper Info
Title
Decomposition of multiple coverings into many parts
Abstract
Suppose that the whole plane (or a large region) is monitored by aset S of stationary sensors such that each element s ∈ S canobserve an axis-parallel unit square R(s) centered at s, whichis called the range of s. Each sensor s is equipped witha battery of unit lifetime. Is it true that if every point of theplane belongs to the range of many sensors, then we can monitorthe plane for a long time without running out of power? If S canbe partitioned into k parts S1, S2,..., Sk such that, foreach i, the sensors in Si together can observe the wholeplane, then the plane can be monitored with no interruption fork units of time. Indeed, we can first switch on all sensorsbelonging to S1. After these sensors run out of battery, we canswitch on all elements of S2, etc.We arrive at the following problem. Let m(k) denote the smallestpositive integer m such that any m-fold covering of the planewith axis-parallel unit squares splits into at least kcoverings. We show that m(k)=O(k2), and generalize this resultto translates of any centrally symmetric convex polygon in theplace of squares. From the other direction, we know only that m(k) ≥ ⌊4k/3⌋ -1.
Year
DOI
Venue
2009
10.1016/j.comgeo.2008.08.002
Computational Geometry: Theory and Applications
Keywords
Field
DocType
k covering,cover decomposition · geometric hypergraphs · centrally symmetric polygons,axis-parallel unit squares split,limited battery life,computational geometry,convex polygon,sensor network problem,multiple covering,coloring,symmetric convex polygon,j. pach,sensor network,sensor networks
Integer,Discrete mathematics,Combinatorics,Foreach loop,Convex polygon,Unit of time,Unit square,Wireless sensor network,Mathematics
Journal
Volume
Issue
ISSN
42
2
Computational Geometry: Theory and Applications
Citations 
PageRank 
References 
29
2.11
15
Authors
2
Name
Order
Citations
PageRank
János Pach12366292.28
Géza Tóth258155.60