(Ford-Fulkerson)

3. (40 pts.) Robust Communications Suppose you are designing a sensor network with sensors si, ..., Sn, which are positioned at different points in the 2D plane and continuously transmit data. You also have antennas a1,..., Am at various locations, which can receive signals from sensors within 1 km. However, antenna i can only connect to mi sensors at a time, so if a sensor is in the range of multiple antennas, you need to be careful about which one to connect to. Furthermore, for redundancy, you want to make sure that every sensor is connected to at least 2 different towers. So the problem is: given the positions of the sensors and antennas, is it possible to assign each sensor to 2 or more antennas within 1 km so that every antenna i is connected to at most m; sensors? Show how to solve this problem by encoding it as an instance of the maximum-flow problem. You should describe both how you build your flow network and how you extract from a maximum flow the assignment of sensors to antennas (or decide one doesn't exist). (Note: If you wish, you may assume the maximum flow you get assigns integer flow to each edge, as the Ford-Fulkerson algorithm returns such a maximum flow when the capacities of the network are integers.)