Obnoxious facility location: Complete service with minimal harm Academic Article uri icon


  • We present efficient algorithms for several instances of the following facility location problem. (Facilities and demand sites are represented as points in the plane.) Place k obnoxious facilities, with respect to n given demand sites and m given regions, where the goal is to maximize the minimal distance between a demand site and a facility, under the constraint that each of the regions must contain at least one facility. We also present an efficient solution to the following planar problem that arises as a subproblem. Given n transmitters, each of range r, construct a compact data structure that supports coverage queries, i.e., determine whether a query polygonal/rectangular region is fully covered by the transmitters. 1 Introduction We consider several instances of the following generally-stated problem, which has several applications in, e.g., urban, industrial and military task planning. Placing Obnoxious Facilities: Let P be a set of n points in the plane (called deman...

publication date

  • January 1, 2000