An incremental version of the k-center problem on boundary of a convex polygon

This paper studies an incremental version of the k-center problem with centers constrained to lie on boundary of a convex polygon. In the incremental k-center problem we considered, we are given a set of n demand points inside a convex polygon, facilities are constrained to lie on its boundary. Our algorithm produces an incremental sequence of facility sets B₁⊆B₂⊆⋯⊆B_n, where each B_k contains k facilities. Such an algorithm is called α-competitive, if for any k, the maximum of the ratio between the value of solution B_k and the value of an optimal k-center solution is no more than α. We present a polynomial time incremental algorithm with a competitive ratio (Formula Presented.) and we also prove a lower bound of 2.