A Simple Algorithm for r-gatherings on the Line - Nakano, Shin-ichi (Journal of Graph Algorithms and Applications, 2019)
In this paper we study a recently proposed variant of the facility location problem called the r-gathering problem. Given sets C and F of points on the plane and distance d(c,f) for each cC and fF, an r-gathering of C to F is an assignment A of C to facilities F^' F such that r or more customers are assigned to each facility in F^'. A facility is open in A if at least one customer is assigned to it. The cost of an r-gathering is the maximum distance d(c,f) between cC and A(c)F' among the assignment, which is _cC{ d(c,A(c)) }. The r-gathering problem finds the r-gathering that minimizes the cost. When all points of C and F are on the line, an O((|C|+|F|)(|C|+|F|) )-time algorithm and an O(|C|+|F|^2 r+|F||F|)-time algorithm to solve the r-gathering problem are known. In this paper we give a simple O(|C|+r^2|F|)-time algorithm to solve the r-gathering problem. Since r<<|F|<<|C| holds in a typical case, say evacuation planning, our new algorithm is O(|F|) factor faster than the known algorithms. We also give an algorithm to solve a simpler problem, called the r-gather-clustering problem, defined as follows. Given a set C of n points on the plane and distance for each pair of points in C, an r-gather-clustering is a partition of the points into clusters such that each cluster has at least r points. The cost of an r-gather-clustering is the maximum radius among the clusters, where the radius of a cluster is the minimum radius of the disk which can cover the points in the cluster. The r-gather-clustering problem is the problem to find the r-gather-clustering that minimizes the cost. In this paper we give an O(rn)-time simple algorithm to solve the problem when all points of C are on the line.