Locating a 1-Center on a Manhattan Plane with "Arbitrarily" Shaped Barriers

Barriers commonly occur in practical location and layout problems and are regions where neither travel through nor location of the new facility is permitted. Along the lines of (Larson and Sadiq, 1983) we divide the feasible location region into cells. To overcome the additional complications introduced by the center objective, we develop new analysis and classify cells based on number of cell comers. A procedure to determine the optimal location is established for each class of cells. The overall complexity of the approach is shown to be polynomially bounded. Also, an analogy is drawn to the center problem on a network and generalizations of the model are discussed.