The 2-center problem with obstacles

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(mlog(2)(mn)+mnlog(2)nlog(mn)). We also present an efficient approximation scheme that constructs, for a given epsilon > 0, two disks as above of radius at most (1+epsilon)r(*), where r(*) is the optimal radius, in time O(1/epsilonlog(1/epsilon)(mlog(2)m+nlog(2)n)) or in randomized expected time O(1/epsilonlog(1/epsilon)((m+nlogn)log(mn))). (C) 2002 Elsevier Science.