Structural Properties of Voronoi Diagrams in Facility Location Problems with Continuous Demand

We consider facility location problems where the demand is continuously and uniformly distributed over a convex polygon with m vertices in the rectilinear plane, n facilities are already present, and the goal is to find an optimal location for an additional facility. Based on an analysis of structural properties of incremental Voronoi diagrams, we develop polynomial exact algorithms for five conditional location problems. The developed methodology is applicable to a variety of other facility location problems with continuous demand. Moreover, we briefly discuss the Euclidean case.