Article ID: | iaor20001371 |
Country: | Netherlands |
Volume: | 93 |
Issue: | 1 |
Start Page Number: | 109 |
End Page Number: | 125 |
Publication Date: | Jun 1999 |
Journal: | Discrete Applied Mathematics |
Authors: | Schbel Anita |
Keywords: | programming: geometric |
In line location problems the objective is to find a straight line which minimizes the sum of distances, or the maximum distance, respectively, to a given 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 through. With the help of a geometric duality we solve such problems for the vertical distance and then extend these results to block norms and some of them even to arbitrary norms. For all norms we give a finite candidate set for the optimal line.