Abstract
Given a set C = {c <sub>1</sub> , C <sub>2</sub> ,...c <sub>2</sub> } of n circles in the plane, in which circle c <sub>i</sub> is centered at point p <sub>i</sub> and has a radius of r <sub>i</sub> , the repeaters allocating problem (RAP) is to allocate a set R = {p <sub>n+ 1</sub> , P <sub>n+2</sub> ..., p <sub>n+m</sub> } of points (called repeaters) in the plane such that G(C, R) is strongly connected and the number of allocated repeaters is minimal; where digraph G(C, R) = (V, E), in which a vertex ν <sub>i</sub> ∈ V stands for the point p <sub>i</sub> , 1 ≤ i ≤ n+ m:, and a directed edge <ν <sub>i</sub> , ν <sub>j</sub> > ∈ E if and only if p <sub>j</sub> is located within the circle of p <sub>i</sub> (the circle of p <sub>k</sub> , n < i <- n + m, is assumed to have a radius of co). In this paper, we show that in the two-dimensional case, the RAP is NP-hard. We also show that the RAP can be reduced to the set covering problem (SCP) so that the approximation algorithms for the SCP can be applied to the RAP. An O(n log n + e) algorithm which uses an O(n) space is also proposed to solve the RAP for the one-dimensional case; here e is the number of edges in G(C, Ø). © 1991 Elsevier Science Publishers B.V.