Solving restricted line location problems via a dual interpretation

In line location problems the objective is to find a straight line which mi nimizes the sum of distances, or the maximum distance, respectively, to a g iven set of existing facilities in the plane. These problems have been well solved. In this paper we deal with restricted line location problems, i.e. we have given a set in the plane where the line is not allowed to pass thr ough. With the help of a geometric duality we solve such problems for the v ertical distance and then extend these results to block norms and some of t hem even to arbitrary norms. For all norms we give a finite candidate set f or the optimal line. (C) 1999 Elsevier Science B.V. All rights reserved.