The (1|1)-Centroid Problem in the Plane with Distance Constraints.

In 1982, Drezner proposed the (1|1)-centroid problem on the plane, in which two players, called the leader and the follower, open facilities to provide service to customers in a competitive manner. The leader opens the first facility, and the follower opens the second. Customers will each patronize the facility closer to them (with ties broken in favor of the first one), thereby deciding the market share of the two facilities. The goal is to find the best position for the leader’s facility so that its market share is maximized. The best algorithm of this problem is an O(n2logn)-time parametric search approach, which searches over the space of market share values. In the same paper, Drezner also proposed a generalized version of (1|1)-centroid problem by introducing a minimal distance constraint R, such that the follower’s facility is not allowed to be located within a distance R from the leader’s. He proposed an O(n5logn)-time algorithm for this generalized version by identifying O(n4) points as the candidates of the optimal solution and checking the market share for each of them. In this paper, we develop a new parametric search approach searching over the O(n4) candidate points, and present an O(n2logn)-time algorithm for this generalized version, thereby closing the O(n3) gap between the two bounds. [ABSTRACT FROM AUTHOR]