Covering a plane with ellipses

Abstract

This paper is devoted to the construction of regular min-density plane coverings with ellipses of one, two and three types. This problem is relevant, for example, to power-efficient surface sensing by autonomous above-grade sensors. A similar problem, for which discs are used to cover a planar region, has been well studied. On the one hand, the use of ellipses generalizes a mathematical problem; on the other hand, it is necessary to solve these types of problems in real applications of wireless sensor networks. This paper both extends some previous results and offers new regular covers that use a small number of ellipses to cover each regular polygon; these covers are characterized by having minimal known density in their classes and give the new upper bounds for densities in these classes as well.

Keywords:

• wireless sensor networks
• plane covering
• coverage density

AMSSubject Classifications:

• 52C15
• 90C27
• 51D20
• 5115
• 5125
• 65K10
• 74P20

Acknowledgments

This research study was supported by the RFBR (grant 13-07-00139-a) and by the Ministry of education and science of the Russian Federation, project 8227.