On the rectangular p-center problem.(English)Zbl 0614.90034

The p-center problem consists in finding the location of p facilities such that any among n given points is as close as possible to anyone of these facilities. In other words minimize the maximal distance of the given points to their nearest facility.
This paper studies ways to solve the p-center problem in the plane, when distances are rectilinear. After describing the well-known O(n) solution method for the 1-center problem, it is shown how the 2-center problem may be solved in O(n) time, and the 3-center problem in O(n log n) time.
Making use of this last result an $$O(n^{2p-5}\log n)$$ algorithm is suggested for cases where $$p>3$$, which can further be simplified into an O(n log$${}^{p-2}n)$$ heuristic.
Reviewer: F.Plastria

MSC:

 90B05 Inventory, storage, reservoirs 68Q25 Analysis of algorithms and problem complexity
Full Text:

References:

 [1] Chen, Naval Research Logistics Quarterly 30 pp 449– (1983) [2] and , ”Location and Layout Planning,” in Lecture Notes in Economics and Mathematical Systems No. 238, 134 pages, Springer-Verlag, Berlin, 1985. · Zbl 0554.90028 [3] Drezner, Journal of the Operational Research Society 35 pp 741– (1984) [4] Drezner, Transportation Science 18 pp 351– (1984) [5] Drezner, SIAM Journal of Algebraic and Discrete Methods 1 pp 315– (1980) [6] Drezner, Computers and Operations Research 12 pp 603– (1985) [7] Elzinga, Transportation Science 6 pp 379– (1972) [8] and , Facility Layout and Location, Prentice-Hall, Englewood Cliffs, NJ, 1974. [9] Hearn, Operations Research 30 pp 777– (1982) [10] Kariv, SIAM Journal of Applied Mathematics 37 pp 513– (1979) [11] Ward, Operations Research 28 pp 836– (1980)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.