Abstract
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 Pach and Tóth. The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ali Abam, M., de Berg, M., Poon, S.: Fault-tolerant conflict-free coloring. In: Proceedings of the Canadian Conference on Computational Geometry (CCCG’08) (2008)
Abellanas, M., Bose, P., Garcia, J., Hurtado, F., Nicolas, C., Ramos, P.: On properties of higher order Delaunay graphs with applications. Int. J. Comput. Geom. Appl. (to appear)
Aloupis, G., Cardinal, J., Collette, S., Langerman, S., Smorodinsky, S.: Coloring geometric range spaces. In: Proceedings of the 8th Latin American Theoretical Informatics (LATIN’08). Lecture Notes in Computer Science, vol. 4957, pp. 146–157. Springer, Berlin (2008)
Brass, P., Moser, W.O.J., Pach, J.: Research Problems in Discrete Geometry. Springer, Berlin (2005)
Buchsbaum, A., Efrat, A., Jain, S., Venkatasubramanian, S., Yi, K.: Restricted strip covering and the sensor cover problem. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’07), pp. 1056–1063 (2007)
Elekes, M., Matrai, T., Soukup, L.: On splitting infinite-fold covers. Fundam. Math. (to appear)
Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33(1), 94–136 (2004)
Gibson, M., Varadarajan, K.: Decomposing coverings and the planar sensor cover problem. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS09) (2009)
Mani, P., Pach, J.: Decomposition problems for multiple coverings with unit balls. Unpublished manuscript (1986)
Pach, J.: Decomposition of multiple packing and covering. In: 2. Kolloq. über Diskrete Geom., pp. 169–178. Inst. Math. Univ. Salzburg, Salzburg (1980)
Pach, J.: Covering the plane with convex polygons. Discrete Comput. Geom. 1, 73–81 (1986)
Pach, J., Tardos, G., Tóth, G.: Indecomposable coverings. In: The China–Japan Joint Conference on Discrete Geometry, Combinatorics and Graph Theory (CJCDGCGT’05). Lecture Notes in Computer Science, vol. 4381, pp. 135–148. Springer, Berlin (2007)
Pach, J., Tóth, G.: Decomposition of multiple coverings into many parts. Comput. Geom. Theory Appl. 42(2), 127–133 (2009)
Pálvölgyi, D.: Indecomposable coverings with concave polygons. Discrete Comput. Geom. (to appear)
Pálvölgyi, D., Tóth, G.: Convex polygons are cover-decomposable. Discrete Comput. Geom. (to appear)
Tardos, G., Tóth, G.: Multiple coverings of the plane with triangles. Discrete Comput. Geom. 38(2), 443–450 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
Part of this work was done while the second and fourth authors where visiting Universidad de Alcalá, under the program Giner de los Ríos.
G. Aloupis, J. Cardinal, S. Collete and S. Langerman are supported by the Communauté Française de Belgique.
D. Orden and P. Ramos are supported by grant MTM2008-04699-C03-02.
S. Collette is Chargé de Recherches du FRS-FNRS.
S. Langerman is Maître de Recherches du FRS-FNRS.
Rights and permissions
About this article
Cite this article
Aloupis, G., Cardinal, J., Collette, S. et al. Decomposition of Multiple Coverings into More Parts. Discrete Comput Geom 44, 706–723 (2010). https://doi.org/10.1007/s00454-009-9238-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-009-9238-3