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.