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 proposedvariant of the facility location problemcalledthe $r$-gathering problem.Given sets $C$ and $F$ of points on the planeand distance $d(c,f)$ for each $c\in C$ and $f\in F$,an $r$-gathering of $C$ to $F$ isan assignment $A$ of $C$ to facilities $F^{'} \subset 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 $c\in C$ and $A(c)\in F'$among the assignment,which is $\max_{c\in C}\{ 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|)\log (|C|+|F|) )$-time algorithm andan $O(|C|+|F|\log^2 r+|F|\log|F|)$-time algorithm to solve the $r$-gathering problem are known.In this paper we give a simple $O(|C|+r^2|F|)$-time algorithmto solve the $r$-gathering problem.Since $r<<|F|<<|C|$ holdsin a typical case, say evacuation planning, our new algorithm is $O(\log |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 planeand distance for each pair of points in $C$,an $r$-gather-clustering is a partition of the pointsinto 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 diskwhich can cover the points in the cluster.The $r$-gather-clustering problem is the problem to findthe $r$-gather-clustering that minimizes the cost.In this paperwe give an $O(rn)$-time simple algorithm to solve the problemwhen all points of $C$ are on the line.