Polynomial algorithms for center location on spheres

Polynomial algorithms for center location on spheres

0.00 Avg rating0 Votes
Article ID: iaor199899
Country: United States
Volume: 44
Issue: 4
Start Page Number: 341
End Page Number: 352
Publication Date: Jun 1997
Journal: Naval Research Logistics
Authors: ,
Abstract:

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 that contains n demand points. The problem is to locate facilities to minimize the maximum distance from any demand point to the closest facility. We present an O(n) algorithm for the one-center problem when a hemisphere contains all demand points and also give an O(n) algorithm for determining whether or not the hemisphere property holds. We present an O(n3 log n) algorithm for the two-center problem for arbitrarily located demand points. Finally, we show that for general p, the p center on a sphere problem is NP-hard.

Reviews

Required fields are marked *. Your email address will not be published.