Locating two obnoxious facilities using the weighted maximin criterion

Given are a finite set of points P and a compact polygonal set S   in R2R2. 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.