Locating a 1-center on a Manhattan plane with ``arbitrarily'' shaped barriers (Q1417711): Difference between revisions

Given a finite set of existing facilities with positive weights (demands) in the plane, the 1-center problem is to find one new location such that the maximum weighted distance to an existing facility is minimized. The paper studies the case where distances are measured by the Manhattan metric and where a finite set of compact (but not necessarily polyhedral or convex) barrier sets restrict traveling. The suggested polynomial time solution method is based on a grid construction introduced by \textit{R. C. Larson} and \textit{G. Sadiq} [Oper. Res. 31, 652--669 (1983; Zbl 0521.90045)] which is extended by so-called equal travel time lines (bisector lines). Extensions to other objective functions that are convex and nondecreasing functions of distances suggest themselves while generalizations to other block norm distances appear to be impossible.