On the complexity of two circle strongly connecting problems
Nen-Fu Huang · IEEE Transactions on Computers · 1992
Given n demand points in the plane, the circle strongly connecting problem (CSCP) is to locate n circles in the plane, each with its center in a different demand point, and determine the radius of each circle such that the corresponding digraph G=(V, E), in which a vertex nu /sub 1/ in V stands for the point p/sub i/, and a directed edge ( nu /sub i/, nu /sub j/) in E, if and only if p/sub j/ located within the circle of p/sub i/, is strongly connected, and the sum of the radii of these n circles is minimal. The constrained circle strongly connecting problem is similar to the CSCP except that the points are given in the plane with a set of obstacles and a directed edge ( nu /sub i/, nu /sub j/) in E, if and only if p/sub j/ is located within the circle of p/sub i/ and no obstacles exist between them. It is proven that both these geometric problems are NP-hard. An O(n log n) approximation algorithm that can produce a solution no greater than twice an optimal one is also proposed.>