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 closing the O(n^3) gap between the two bounds.

A prototype is representative of a set of similar objects. This paper proposes an approach that formulates the problem of prototype generation as finding the mean from a given set of objects, where the prototype solution must satisfy certain constraints. These constraints describe the important perceptual features of the sample shapes that the proposed prototype must retain. The contour prototype generated from a set of planar objects was used as an example of the approach, and the corners were used as the perceptual features to be preserved in the proposed prototype shape. However, finding a prototype solution for more than two contours is computationally intractable. A tree-based approach is therefore proposed in which an efficient greedy random algorithm is used to obtain a good approximation of the proposed prototype and analyze the expected complexity of the algorithm. The proposed prototype-generation process for hand-drawn patterns is described and discussed in this paper.