Competitive location with rectilinear distances

In this paper we consider the problem of locating new facilities which will compete with the existing ones for providing goods or services to n customers. It is assumed that a customer will change his habit and use a new facility if among the new facilities there is one that is closer to him than the closest old facility. Then the problem consists in finding the location of one or several new facilities in order to maximize the sum of the weights of the customers attracted by these new facilities. The problem of locating one new facility is solved using an algorithm in time O(n³). Moreover, an algorithm in time O(n⁵) is proposed for the case of two new facilities.