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.0552Last 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.

Related papers

Commercial Disclosure
© 2023 Paper Studio™. All Rights Reserved.