Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Variable-Size Rectangle Covering
verfasst von : Francis Y. L. Chin, Hing-Fung Ting, Yong Zhang
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
(
n
log
n
) and
O
(
n
)).