Solving rectilinear planar location problems with barriers by a polynomial partitioning (Q1872030)

The reduced domain obtained in the companion paper [ibid. 111, 89--110 (1992; Zbl 1041.90026)] is further split into a network connecting the fixed points and a polynomial number of convex cells. Each barrier \(l_1\)-distance to a fixed point equals the shortest path distance on the network, and is linear on each cell. Minimising any nondecreasing convex function of these distances is thereby reduced to a location problem on a network and a finite number of constrained convex minimisation problems, all solvable by standard methods.