POLYNOMIAL ALGORITHMS FOR CENTER LOCATION ON SPHERES

When locating facilities over the earth or in space, a planar location model is no longer valid and we must use a spherical surface. In this article, we consider the one- and two-center problems on a sphere tha t contains n demand points. The problem is to locate facilities to min imize the maximum distance from any demand point to the closest facili ty. We present an O(n) algorithm for the one-center problem when a hem isphere contains all demand points and also give an O(n) algorithm for determining whether or not the hemisphere property holds. We present an O(n(3) log n) algorithm for the two-center problem for arbitrarily located demand points. Finally, we show that for general p, the p cent er on a sphere problem is NP-hard. (C) 1997 John Wiley & Sons, Inc.