Station layouts in the presence of location constraints

Prosenjit Bose, Christos Kaklamanis, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, David Peleg

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In wireless communication, the signal of a typical broadcast station is transmited from a broadcast center p and reaches objects at a distance, say, R from it. In addition there is a radius r, r < R, such that the signal originating from the center of the station is so strong that human habitation within distance r from the center p should be avoided. Thus every station determines a region which is an “annulus of permissible habitation". We consider the following station layout (SL) problem: Cover a given (say, rectangular) planar region which includes a collection of orthogonal 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 building is within the dangerous range of a station. We give algorithms for computing such station layouts in both the one-and two-dimensional cases.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 10th International Symposium, ISAAC 1999, Proceedings
EditorsC. Pandu Rangan, Alok Aggarwal
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540669167, 9783540669166
StatePublished - 1999
Event10th Annual International Symposium on Algorithms and Computation, ISAAC 1999 - Chennai, India
Duration: Dec 16 1999Dec 18 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference10th Annual International Symposium on Algorithms and Computation, ISAAC 1999

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Station layouts in the presence of location constraints'. Together they form a unique fingerprint.

Cite this