One generalization of the Weber problem is to locate not a single point, but dimensional facilities such as lines, segments, paths or trees. In this paper we deal with locating a line in the plane. If d is a distance measure our objective is to find a straight line l which minimizes f(l) = ∑Mm=1 wmd(Exm,l) where wm ≥ 0 are non-negative weights, Exm = (am1,am2), m = 1, …, M, are the M existing facilities represented by points in the plane and d(Exm,l) = min P∈l d(Exm,P) is the distance from the existing facility Exm to the line l. If d is the Euclidean or rectangular distance, efficient algorithms to find the optimal line are known. This paper considers the case that d is a block norm. An efficient algorithm will be developed and we will prove that there always exists an optimal line passing through at least two of the existing facilities. The results are a generalization of the l1-case. They are also extended to the question of finding the best central line, i.e., a line l such that maxm=1,…,M d(l,Exm) is minimised.
