Decomposition of multiple coverings into more parts

ABSTRACT

We 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 (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.

REFERENCES

• 1: G. Aloupis, J. Cardinal, S. Collette, S. Langerman, and S. Smorodinsky. Coloring geometric range spaces. In Proceedings of the 8th Latin American Theoretical Informatics (LATIN'08), Lecture Notes in Computer Science, pages 146--157. Springer-Verlag, 2008.
• 2: P. Brass, W. O. J. Moser, and J. Pach. Research Problems in Discrete Geometry. Springer-Verlag, 2005.
• 3: Adam L. Buchsbaum , Alon Efrat , Shaili Jain , Suresh Venkatasubramanian , Ke Yi, Restricted strip covering and the sensor cover problem, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1056-1063, January 07-09, 2007, New Orleans, Louisiana
• 4: M. Elekes, T. Matrai, and L. Soukup. On splitting infinite-fold covers. Unpublished manuscript, 2007.
• 5: P. Mani and J. Pach. Decomposition problems for multiple coverings with unit balls. Unpublished manuscript, 1986.
• 6: J. Pach. Decomposition of multiple packing and covering. In 2. Kolloq. über Diskrete Geom., pages 169--178. Inst. Math. Univ. Salzburg, 1980.
• 7: János Pach, Covering the plane with convex polygons, Discrete & Computational Geometry, v.1 n.1, p.73-81, 1986 [doi>10.1007/BF02187684]
• 8: J. Pach, G. Tardos, and G. Tóth. Indecomposable coverings. In The China--Japan Joint Conference on Discrete Geometry, Combinatorics and Graph Theory (CJCDGCGT'05), Lecture Notes in Computer Science, pages 135--148, 2007.
• 9: Janos Pach , Geza Toth, Decomposition of multiple coverings into many parts, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247096]
• 10: D. Pálvölgyi and G. Tóth. Private communication. 2008.
• 11: Gabor Tardos , Geza Toth, Multiple Coverings of the Plane with Triangles, Discrete & Computational Geometry, v.38 n.2, p.443-450, September 2007 [doi>10.1007/s00454-007-1345-4]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems