$\underline{\textbf{Facts:}}$
1. $N$ towers are installed over some area $A$
2. Company provides services of $k$ frequencies
3. $N\ge k$
$\underline{\textbf{Objective:}}$
To design an algorithm that outputs "feasible" when all the $k$ frequencies can be provided as service over all the $N$ towers, else the minimum number of frequencies needed to cover all the $N$ towers.
Under this scenario, particular problem will have a trivial solution of being "feasible" every time. Hence we are provided with certain constraints.
$\underline{\textbf{Constraints:}}$
Two towers broadcasting on same frequency are greater than equal to $R$ KM apart.
$\underline{\textbf{Design:}}$
We can use graphs to model this problem, where vertex would represent towers and edges between any two towers would indicate distance between them, forming an undirected simple complete graph on $N$ vertices. Lets' notate this graph as $G(V,E)$.
$\underline{\textbf{Preliminary Observations:}}$
$\forall_{u,v \ \in \ V} \ D(u,v)<R \implies f(u) \neq f(v)$, where $V$ is the set of vertices/towers, $D:V \times V \rightarrow \mathbb{R}$ is distance between two towers, $f:V \rightarrow [k]$ is frequency assignment function to any tower. $[k] = \{1,2,\dots,k\}$
$\forall_{u,v \ \in \ V} \ D(u,v)\ge R \implies [f(u) \neq f(v)]\lor [f(u) = f(v)]$. So frequency assignment doesn't have any constraints until and unless distance between them is greater than equal to $R$ KM.
$\underline{\textbf{Re-Design:}}$
Since frequency assignment is dependent on distances less than $R$ KM, then we can remove the edges with greater than equal to $R$ KM distance. Lets' notate this graph as $\overline{G}(V, \overline{E})$
$\underline{\textbf{Idea:}}$
Finding minimal number of frequency assignments over $N$ towers where no two connected towers have same frequency (definition of $\textbf{Graph Coloring}$) can tell us if its' feasible to provide services on $k$ frequencies or not.
When $\chi(\overline{G}) \le k$ then $\overline{G}$ is $k$-colorable too. Here, $\chi(\cdot)$ is chromatic number. However, $\overline{G}$ is not $k$-colorable if $\chi(\overline{G})>k$. Hence, finding chromatic number can get the job done.
$\underline{\textbf{Algorithm:}}$
$\underline{\text{Step 1}}:$ Design the data structure for graph $G$
$\underline{\text{Step 2}}:$ Remove edges with distance more than equal to $R$ KM and call this $\overline{G}$
Output = $\begin{cases}\text{feasible} & \chi(\overline{G}) \le k \\ \chi(\overline{G}) & \chi(\overline{G}) > k \end{cases}$