An international cellphone company provides service on 7 different frequencies. They wish to set up business in Tamil Nadu and have fixed the locations of 100 towers for their new service. The company has to ensure that two towers broadcasting on the same frequency are at least 100 km apart, so that there is no interference of signals.
(i) Model this problems using graphs.
(ii) Describe an algorithm which will answer the question “Is it feasible to set up towers at the given locations and provide service on 7 different frequencies?”. Your algorithm should say “feasible” if it is feasible, otherwise output the minimum number of frequencies needed to utilize all 100 towers.
