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.
- N. Alon and J.H. Spencer: The Probabilistic Method (2nd ed.), Wiley, New York, 2000.Google Scholar
- P. Erdos and L. Lovász: Problems and results on 3-chromatic hypergraphs and some related questions, in: Infinite and Finite Sets (Colloq., Keszthely, 1973; dedicated to P. Erdos on his 60th birthday), Vol. II, Colloq. Math. Soc. János Bolyai 10, North-Holland, Amsterdam, 1975, 609--627.Google Scholar
- A. Buchsbaum, A. Efrat, S. Jain, S. Venkatasubramanian, and K. Yi: Restricted strip covering and the sensor cover problem, Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA '07) New Orleans, 2007. Google ScholarDigital Library
- U. Feige, M. M. Halldórsson, G Kortsarz, and A. Srinivasan: Approximating the domatic number, SIAM J. Computing 32 (2002), 172--195. Google ScholarDigital Library
- G. Fejes Tóth: New results in the theory of packing and covering, in: Convexity and its Applications (P.M. Gruber, J.M. Wills, eds.), Birkhäuser, Basel, 1983, 318--359.Google Scholar
- G. Fejes Tóth and W. Kuperberg: A survey of recent results in the theory of packing and covering, in: New Trends in Discrete and Computational Geometry (J. Pach, ed.), Algorithms Combin. 10, Springer, Berlin, 1993, 251--279.Google Scholar
- B. Liu and D. Towsley: On the coverage and detectability of large-scale wireless sensor networks. Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks Conference (WiOpt), 2003.Google Scholar
- P. Mani and J. Pach: Decomposition problems for multiple coverings with unit balls, manuscript, 1986.Google Scholar
- J. Pach: Decomposition of multiple packing and covering, 2. Kolloquium über Diskrete Geometrie, Salzburg (1980), 169--178.Google Scholar
- J. Pach: Covering the Plane with Convex Polygons, Discrete and Computational Geometry 1 (1986), 73--81. Google ScholarDigital Library
- J. Pach, G. Tardos, and G. Tóth: Idecomposable coverings in: The China-Japan Joint Conference on Discrete Geometry, Combinatorics and Graph Theory (CJCDGCGT 2005), Lecture Notes in Computer Science, Springer, accepted. Google ScholarDigital Library
- S. Smorodinsky: Personal communication, May 2006.Google Scholar
- G. Tardos and G. Tóth: Multiple coverings of the plane with triangles, Discrete Comput. Geom., accepted. Google ScholarDigital Library
- D. Tian and N. Georganas: A coverage-preserving node scheduling scheme for large wireless sensor networks, Proc. ACM Workshop on Wireless Sensor Networks and Applications, Atlanta, 2002, 32--41. Google ScholarDigital Library
- F. Ye, G. Zhong, S. Lu, and L. Zhang: PEAS: A robust energy conserving protocol for long-lived sensor networks, 3rd International Conference on Distributed Computing Systems (ICDCS '03), Rhode Island, 2003.Google Scholar
Index Terms
- Decomposition of multiple coverings into many parts
Recommendations
Decomposition of multiple coverings into many parts
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. J. Pach [J. Pach, Covering the plane with convex polygons, Discrete and Computational Geometry 1 ...
Decomposition of Multiple Coverings into More Parts
We prove that for every centrally symmetric convex polygon Q, there exists a constant ź such that any locally finite źk-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by ...
Decomposition of multiple coverings into more parts
SODA '09: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithmsWe prove that for every centrally symmetric convex polygon Q, there exists a constant α such that any αK-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Tóth (...
Comments