Given are a finite set of points P and a compact polygonal set S in R2. The problem is to locate two new facilities in S, maximizing the minimum of all weighted distances between the points in P and the two new facilities, and the distance between the pair of new facilities. We present subquadratic algorithms.
