Premium
Polynomial algorithms for center location on spheres
Author(s) -
Jaeger Mordechai,
Goldberg Jeff
Publication year - 1997
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199706)44:4<341::aid-nav4>3.0.co;2-6
Subject(s) - center (category theory) , point (geometry) , algorithm , planar , surface (topology) , spheres , computer science , mathematics , facility location problem , mathematical optimization , combinatorics , geometry , computer graphics (images) , engineering , aerospace engineering , chemistry , crystallography
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(n 3 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. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 341–352, 1997