subject

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))

ansver
Answers: 1

Other questions on the subject: Computers and Technology

image
Computers and Technology, 23.06.2019 09:30, blake2001
Which of the following tasks is an audio technician most likely to perform while working on a nature documentary? (select all that apply). eliminating potentially distracting background noise adding sound effects making sure the lighting is adequate for a particular scene changing the narration to better match the mood of the documentary
Answers: 3
image
Computers and Technology, 23.06.2019 16:30, 19thomasar
How to do this programming flowchart?
Answers: 3
image
Computers and Technology, 24.06.2019 15:30, lizziesuks
What is the function of compilers and interpreters? how does a compiler differ from an interpreter?
Answers: 2
image
Computers and Technology, 24.06.2019 18:30, shemiahking5432
Jacking is a crime that takes place when a hacker misdirects url to a different site. the link itself looks safe, but the user is directed to an unsafe page
Answers: 1
You know the right answer?
You can tell that cellular phones are at work in rural communities, from the giant microwave towers...

Questions in other subjects:

Konu
Mathematics, 21.10.2019 13:30
Konu
History, 21.10.2019 13:30