A Simple Algorithm for $r$-gatherings on the Line

Abstract

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 $c\in C$ and $f\in F$, an $r$-gathering of $C$ to $F$ is an 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 and an $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 algorithm to solve the $r$-gathering problem. Since $r<<|F|<<|C|$ holds in 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 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.