In the (
r | p
)-centroid problem, two players, called leader and follower, open facilities to service clients. We assume that clients are identified with their location on the Euclidian plane, and facilities can be opened anywhere in the plane. The leader opens
facilities. Later on, the follower opens
facilities. Each client patronizes the closest facility. Our goal is to find
facilities for the leader to maximize his market share. For this Stackelberg game we develop a new alternating heuristic, based on the exact approach for the follower problem. At each iteration of the heuristic, we consider the solution of one player and calculate the best answer for the other player. At the final stage, the clients are clustered, and an exact polynomial-time algorithm for the (1
1)-centroid problem is applied. Computational experiments show that this heuristic dominates the previous alternating heuristic of Bhadury, Eiselt, and Jaramillo.