Planar location problems with block distance and barriers

This paper considers one facility planar location problems using block distance and assuming barriers to travel. Barriers are defined as generalized convex sets relative to the block distance. The objective function is any convex, nondecreasing function of distance. Such problems have a non-convex feasible region and a non-convex objective function. The problem is solved by modifying the barriers to obtain an equivalent problem and by decomposing the feasible region into a polynomial number of convex subsets on which the objective function is convex. It is shown that solving a planar location problem with block distance and barriers requires at most a polynomial amount of additional time over solving the same problem without barriers.