You can tell that cellular phones are at work in rural communities, from the giant microwave towers you sometimes see sprouting out of corn fields and cow pastures. Let's consider a very simplified model of a cellular phone network in a sparsely populated area. We are given the locations of n base stations, specified as points b1,,bn in the plane. We are also given the locations of n cellular phones, specified as points p1, ...,pn in the plane. Finally, we are given a range parameter A > 0. We call the set of cell phones fully connected if it is possible to assign each phone to a base station in such a way that ⢠Each phone is assigned to a different base station, and
⢠If a phone at pt is assigned to abase station at bj, then the straight-line distance between the points pi and bj is at most A.
Suppose that the owner of the cell phone at point p1 decides to go for a drive, traveling continuously for a total of z units of distance due east. As this cell phone moves, we may have to update the assignment of phones to base stations (possibly several times) in order to keep the set of phones fully connected Give a polynomial-time algorithm to decide whether it is possible to keep the set of phones fully connected at all times during the travel of this one cell phone. (You should assume that all other phones remain stationary during this travel.) If it is possible, you should report a sequence of assignments of phones to base stations that will be sufficient in order to maintain full connectivity; if it is not possible, you should report a point on the traveling phone's path at which full connectivity cannot be maintained.
You should try to make your algorithm run in O(n3) time if possible
Example. Suppose we have phones at p1 = (0, 0) and p2 = (2, 1); we have base stations at bl (1, 1) and b2 - (3, 1); and A2. Now consider the case in which the phone at p1 moves due east a distance of 4 units, ending at (4, 0). Then it is possible to keep the phones fully connected during this motion: We begin by assigning p1 to b1 and p2 to b2, and we reassign p1 to b2 and p2 to b1 during the motion (for example, when p1 passes the point (2, 0))