Decomposition of Multiple Coverings into More Parts
G. Aloupis and J. Cardinal and S. Collette and S. Langerman and D. Orden and P. Ramos
Arxiv ID: 0807.0552•Last updated: 7/21/2020
We prove that for every centrally symmetric convex polygon Q, there exists a constant alpha such that any alpha*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 Toth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery lifetime.
PaperStudio AI Chat
I'm your research assistant! Ask me anything about this paper.