  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 then the follower opens the second. Each customer will patronize
the facility closest to him (ties broken in favor of the leader's one), thereby
decides the market share of the two players. The goal is to find the best
position for the leader's facility so that his market share is maximized. The
best algorithm for this problem is an $O(n^2 \log n)$-time parametric search
approach, which searches over the space of possible market share values.
  In the same paper, Drezner also proposed a general 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(n^5 \log n)$-time algorithm for this general
version by identifying $O(n^4)$ 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(n^4)$ candidate
points, and present an $O(n^2 \log n)$-time algorithm for the general version,
thereby close the $O(n^3)$ gap between the two bounds.
