Polynomial algorithms for restricted Euclidean p-centre problems

AbstractGiven 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 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