26. You can tell that cellular phones are at work in rural communities, from the

Question

26. 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 bi,..., bn in the plane. We are also given the locations of n cellular phones, specified as points pi, , Pn in the plane. Finally, we are given a range parameter >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 p, is assigned to a base station at b, then the straight-line distance between the points pi and bj is at most . Suppose that the owner of the cell phone at point pi 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 sta tionary 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 pl= (0,0) and p2= (2, 1); we have base stations at bl = (1, 1) and b2= (3, 1); and =2. Now consider the case in which the phone at pi moves due east a distance of 4 units, ending at (4, 0). Then it is possible to keep the phones fully connected during this

Explanation / Answer

A standard application of maximum ow computation is to decide if the set of cell phones fully connected. To do this consider a graph whose nodes are the cell phones and the base stations with an edge from a cell phone c to a base station b if c is in range from station b. We add a sources and connect it to each cell phone via an edge of capacity 1, and add a sink t and connect each base station to t with an edge of capacity 1. See the Figure 3 below for an example. We claim that a set of n cell phones is fully connected if and only if the maximum ow in this network has value n.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.