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 S₁, S₂,..., S_k such that, foreach i, the sensors in S_i 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 S₁. After these sensors run out of battery, we canswitch on all elements of S₂, 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(k²), 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.

REFERENCES

• 1: N. Alon and J.H. Spencer: The Probabilistic Method (2nd ed.), Wiley, New York, 2000.
• 2: 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.
• 3: 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.
• 4: Uriel Feige , Magnús M. Halldórsson , Guy Kortsarz , Aravind Srinivasan, Approximating the Domatic Number, SIAM Journal on Computing, v.32 n.1, p.172-195, 2003 [doi>10.1137/S0097539700380754]
• 5: 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.
• 6: 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.
• 7: 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.
• 8: P. Mani and J. Pach: Decomposition problems for multiple coverings with unit balls, manuscript, 1986.
• 9: J. Pach: Decomposition of multiple packing and covering, 2. Kolloquium über Diskrete Geometrie, Salzburg (1980), 169--178.
• 10: János Pach, Covering the plane with convex polygons, Discrete & Computational Geometry, v.1 n.1, p.73-81, 1986 [doi>10.1007/BF02187684]
• 11: 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.
• 12: S. Smorodinsky: Personal communication, May 2006.
• 13: G. Tardos and G. Tóth: Multiple coverings of the plane with triangles, Discrete Comput. Geom., accepted.
• 14: Di Tian , Nicolas D. Georganas, A coverage-preserving node scheduling scheme for large wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570744]
• 15: 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Theory

Keywords:
multiple coverings, sensor networks