An equivalence result for single facility planar location problems with rectilinear distance and barriers

This paper considers planar location problems with rectilinear distance and barriers, where the objective function is any convex, nondecreasing function of distance. Such problems have a non-convex feasible region and a non-convex objective function. A modification of the barriers is developed based on properties of the rectilinear distance. It is shown that the original problem with barriers is equivalent to the problem with modified barriers. A particular modification is given that reduces the feasible region and permits its partitioning into convex subsets on which the objective function is convex. A solution algorithm based on the partitioning is the subject of a companion paper.