Polynomial algorithms for restricted Euclidean p-centre problems (Q1116694)

Given n demand points in the plane, the p-centre problem is to locate p supply points so as to minimize the maximum distance from a demand point to its nearest supply point. Megiddo and Supowit have recently shown [\textit{N. Megiddo} and \textit{K. J. Supovit}, SIAM J. Comput. 13, 182-196 (1984; Zbl 0534.68032)] that not only is this problem NP-hard, but even finding a close approximate solution to the problem is NP-hard. In this paper we present a polynomial time algorithm for the Euclidean p-centre problem when the demand points are restricted to lie on a fixed number of parallel lines.