Abstract
Given n demand points in the plane, the circle connecting problem (CCP) is to locate n circles in the plane, each with its center in a demand point, and determine the radius of each circle such that the corresponding undirected graph G = (V, E), in which a vertex v i in V stands for the point p i and an edge (v i , v j ) in E if and only if p i and p j are located within the circle of each other, is connected, and the sum of the radii of these n circles is minimal. The constrained circle connecting problem is similar to the CCP except that the points are given in a plane with a set of obstacles and an edge (v i , v j ) in E if and only if p i and p j are located within the circle of each other and no obstacles exist between them. In this paper, we show that both these geometric problems are NP-hard. An O(n log n) time divide-and-conquer approximation algorithm that produces a solution no greater than twice an optimal one is also proposed for the two problems. Experimental results show that in the average case the approximate solution is close to the optimal solution. © 1993.