A linear time algorithm for the r-gathering problem on the line

Abstract In this paper, we revisit the r-gathering problem. Given sets C and F of points on the plane and distance d ( c , f ) for each c ∈ C and f ∈ F , an r-gathering of C to F is an assignment A of C to open facilities F ′ ⊆ F such that r or more members of C are assigned to each open facility. The cost of an r-gathering is max c ∈ C ⁡ d ( c , A ( c ) ) . The r-gathering problem computes the r-gathering minimizing the cost. In this paper we study the r-gathering problem when C and F are on a line and present a O ( | C | + | F | ) -time algorithm to solve the problem. Our solution is optimal since any algorithm needs to read C and F at least once.