Premium
On the rectangular p ‐center problem
Author(s) -
Drezner Zvi
Publication year - 1987
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/1520-6750(198704)34:2<229::aid-nav3220340207>3.0.co;2-1
Subject(s) - center (category theory) , mathematics , combinatorics , computer science , algorithm , crystallography , chemistry
The p ‐center problem involves finding the best locations for p facilities such that the furthest among n points is as close as possible to one of the facilities. Rectangular (sometimes called rectilinear, Manhattan, or l 1 ) distances are considered. An O(n) algorithm for the 1‐center problem, an O(n) algorithm for the 2‐center problem, and an O(n log n ) algorithm for the 3‐center problem are given. Generalizations to general p ‐center problems are also discussed.