Conditional facility location problems in the rectilinear plane with piecewise polynomial demand

This paper considers facility location problems where n facilities exist within a convex polygon in the rectilinear plane, across which a piecewise polynomial demand function is distributed. The optimal location for an additional facility is sought in order to optimise a variety of common facility location objectives. After an in-depth analysis of the structural properties of the overlay of incremental Voronoi diagrams and polygonal demand distributions, along with the analysis of algebraic representations of the objective functions for five conditional facility location problems, it is proven that a polynomial exact algorithm exists if the demand is piecewise uniform or piecewise linear (depending on the specific location problem studied) over the polygon. This polynomial exact algorithm makes use of a triangular decomposition of the incremental Voronoi diagram and first-order optimality conditions, and is applicable to location problems for various families of demand functions. The results in this paper may also be adapted to obtain similar conclusions for other classic location problems that are briefly mentioned.