Polynomial algorithms for center location on spheres

✍ Scribed by Mordechai Jaeger; Jeff Goldberg

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 72 KB
• Volume: 44
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/(sici)1520-6750(199706)44:4<341::aid-nav4>3.0.co;2-6

✦ Synopsis

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 oneand 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.