In this paper, we introduce a new constrained version of the center problem in which the location of each center is laid only on the boundary of a given convex $m$-gon representing obstacle. Using Megiddo's parameter searching technique, an $O(n log^2 mn log n+m)$ time algorithm is proposed. If n is a constant, time complexity of the proposed algorithm is linear. We can apply the algorithm to locating entrances of a garden and ports on a island.
It is for the first time for the κ-center problem on the convex polygon boundary to be solved. The general κ-center problem is NP-complete when κ is a part of the input. But the parameter κ does not increase the time complexity of the proposed algorithm.
