Problem 1: 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, B₁, B₂, , B_K , will be specified by B_i(x, y), the x and y coordinates in the plane of base station B_i. 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, C₁, C₂, , C_N positioned in the town at coordinates C_i(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.