The half-line centre problem with l1(l∞) Metrics

This paper deals with a minimax location problem consisting in the location of a radial facility emanating from a given point P0 when using l1- and l∞-norm. For the general problem an O(n² log n) time algorithm is obtained via case analysis. When the point P0 is outside the convex hull of the demand points, a linear algorithm is devised. This procedure helps to improve the algorithm for the case in which P0 belongs to the convex hull to an O(n²) time algorithm.