Problem 2: Testing Base Station Coverage

A town is planning on where to place the base stations for a new wireless technology. It wants to test the coverage of a set of k base station locations before it goes to the expense of building them. The base station positions, B1, B2, …, BK , will be specified by Bi(x, y), the x and y coordinates in the plane of base station Bi. The town wants you to design an algorithm that will test how well the base stations serve N mobile clients in a specific scenario. The scenario is consist n mobile clients, C1, C2, …, CN positioned in the town at coordinates Ci(x, y).

Each client will be connected to exactly one base station. However, the base stations have limited range. A client can only be connected to a base station within distance R – distance can be thought of as the usual Euclidean distance in the x, y coordinates. Finally, there is a load parameter L – no more than L clients can be connected to any single base station.

Specify a flow network to solve this problem including any data structures. You must use the notation in the problem and draw a picture so the representation is easy for a human to understand!

1. Specify what each node, edges, and edge capacities represent in the network.

2. How to determine which mobile clients are assigned to which base stations for a given scenario.