Variable-size rectangle covering

Abstract

In wireless communication networks, optimal use of the directional antenna is very important. The directional antenna coverage (DAC) problem is to cover all clients with the smallest number of directional antennas. In this paper, we consider the variable-size rectangle covering (VSRC) problem, which is a transformation of the DAC problem. There are n points above the base line y=0 of the two-dimensional plane. The target is to cover all these points by minimum number of rectangles, such that the dimension of each rectangle is not fixed but the area is at most 1, and the bottom edge of each rectangle is on the base line y=0. In some applications, the number of rectangles covering any position in the two-dimensional plane is bounded, so we also consider the variation when each position in the plane is covered by no more than two rectangles. We give two polynomial time algorithms for finding the optimal covering. Further, we propose two 2-approximation algorithms that use less running time (O(nlogn) and O(n)). © 2009 Springer Berlin Heidelberg.