STATION LAYOUTS IN THE PRESENCE OF LOCATION CONSTRAINTS
Prosenjit K. Bose, Evangelos Kranakis, Christos Kaklamanis, Lefteris M. Kirousis, Danny Kriz̧anc, David Peleg · Journal of Interconnection Networks · 2002
In wireless communication, the signal of a typical broadcast station is transmitted from a broadcast center p and reaches objects at a distance, say, r from it. In addition there is a radius r0, r0 < r, such that the signal originating from the center of the station is so strong that human habitation within distance r0 from the center p should be avoided. In other words, points within distance r0 from the station comprise a hazardous zone. We consider the following station layout proble: Cover a given planar region that includes a collection of buildings with a minimum number of stations so that every point in the region is within the reach of a station, while at the same time no interior point of any building is within the hazardous zone of a station. We give algorithms for computing such station layouts in both the one- and two-dimensional cases.