OPTIMAL MULTIFACILITY DEFENSIVE LOCATION ON PLANES WITH RECTILINEAR DISTANCES

In this paper, we are concerned with the problem of optimally covering a large region with rectilinear distances by many service facilities. We assume that the number of customers is proportional to the area th at they occupy and that each customer patronizes the nearest facility. Our objective is to locate the facilities in such a manner that the m aximal area any future competitor facility can capture will be minimiz ed. For Euclidean distances, it has been conjectured that the best arr angement is a triangular grid, yielding hexagonal service areas (honey comb). In this paper, we show that an analogous arrangement is optimal for rectilinear distances. Furthermore, as in the Euclidean case, it minimizes both the average and the maximal distance for all customers to their nearest facilities. The service areas under the optimal solut ion are rectilinear circles-which are shaped as Euclidean squares tilt ed at 45-degrees to the X- and Y-axes. (C) 1993 by John Wiley & Sons, Inc.