Algorithm Analysis]

Suppose you work for the government to approve the radio stations their requested radio

frequency. Recently there has been hundreds of requests from radio stations to transmit on

radio frequency 90.0 FM. You have no problem to grant these requests, but no two requesting

locations can be within 25 miles of each other. Lets say, 1 euclidean distance 2 25 miles. If

any two locations are within distance of 1, you will probably dump all the requests.

Each requests consists of the coordinates (any) of the radio stations. No requests have

conicting at and y coordinate. You are given the requests in two sorted lists, RX which

consists of the requests sorted by x component and Ry, sorted by y component.

1. If you map the requests on a square grid, each square would have the dimension

0.5 a: 0.5. Would you cancel the set of requests if two of them are on the boundary of

the same square?

2. Design an algorithm to determine if the request set contains any two cases that are

within ED (euclidean distance) 1 of each other. If it does, your algorithm should

return the guilty pair. Your algorithm must run in O( n log n ) [n = the number of

requests] Hint: Use divideandconquer.

3. How would you modify your algorithm of part (2) to determine whether there are three

or more requests within ED distance of 1 to each other. Your algorithm should maintain

the same time complexity as part 2.