Planar Weber location problems with barriers and block norms

Weber problem for a given finite set of existing facilities epsilonx = {Ex( 1), Ex(2),..., Ex(M)} subset of R-2 with positive weights w(m) (m = 1,..., M) is to find a new facility X* is an element of R-2 such that Sigma (m=1) (M) w(m)d(X, Ex(m)) is minimized for some distance function d. In this pape r we consider distances defined b block norms. A variation of this problem is obtained if barriers are introduced which ar e convex polyhedral subsets of the plane where neither location of new faci lities nor traveling is allowed. Such barriers, like lakes, military region s, national parks or mountains, are frequently encountered in practice. From a mathematical point of view barrier problems are difficult, since the presence of barriers destroys the convexity of the objective function. Nev ertheless, this paper establishes a discretization result: one of the grid points in the grid defined by the existing facilities and the fundamental d irections of the polyhedral distances can be proved to be an optimal locati on. Thus the barrier problem can be solved with a polynomial algorithm.