Given a set S of n points in the plane and a set 0 of pairwise disjoint simple polygons with a total of m edges, we wish to find two congruent disks of smallest radius whose union covers S and whose centers lie outside the polygons in O (referred to as locational constraints in facility location theory). We present an algorithm to solve this problem in randomized expected time O(m log2(mn) + mn log2(n) log(mn)). We also present an efficient approximation scheme that constructs, for a given ε > 0, two disks as above of radius at most (1 + ε)r*, where r* is the optimal radius, in time O(1/ε) log(1/ε)(m log2(m) + n log2(n)) or in randomized expected time O(1/ε) log(1/ε) ((m + nlog(n))log(mn))).
