Station layouts in the presence of location constraints

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

doi:10.1007/3-540-46632-0_28

Station layouts in the presence of location constraints

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English (US)
Title of host publication	Algorithms and Computation - 10th International Symposium, ISAAC 1999, Proceedings
Editors	C. Pandu Rangan, Alok Aggarwal
Publisher	Springer Verlag
Pages	269-278
Number of pages	10
ISBN (Print)	3540669167, 9783540669166
DOIs	https://doi.org/10.1007/3-540-46632-0_28
State	Published - 1999
Event	10th Annual International Symposium on Algorithms and Computation, ISAAC 1999 - Chennai, India Duration: Dec 16 1999 → Dec 18 1999

Publication series

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

Conference

Conference	10th Annual International Symposium on Algorithms and Computation, ISAAC 1999
Country/Territory	India
City	Chennai
Period	12/16/99 → 12/18/99

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-46632-0_28

Cite this

Bose, P., Kaklamanis, C., Kirousis, L. M., Kranakis, E., Krizanc, D., & Peleg, D. (1999). Station layouts in the presence of location constraints. In C. P. Rangan, & A. Aggarwal (Eds.), Algorithms and Computation - 10th International Symposium, ISAAC 1999, Proceedings (pp. 269-278). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1741). Springer Verlag. https://doi.org/10.1007/3-540-46632-0_28

Station layouts in the presence of location constraints. / Bose, Prosenjit; Kaklamanis, Christos; Kirousis, Lefteris M. et al.
Algorithms and Computation - 10th International Symposium, ISAAC 1999, Proceedings. ed. / C. Pandu Rangan; Alok Aggarwal. Springer Verlag, 1999. p. 269-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1741).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bose, P, Kaklamanis, C, Kirousis, LM, Kranakis, E, Krizanc, D & Peleg, D 1999, Station layouts in the presence of location constraints. in CP Rangan & A Aggarwal (eds), Algorithms and Computation - 10th International Symposium, ISAAC 1999, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1741, Springer Verlag, pp. 269-278, 10th Annual International Symposium on Algorithms and Computation, ISAAC 1999, Chennai, India, 12/16/99. https://doi.org/10.1007/3-540-46632-0_28

Bose P, Kaklamanis C, Kirousis LM, Kranakis E, Krizanc D, Peleg D. Station layouts in the presence of location constraints. In Rangan CP, Aggarwal A, editors, Algorithms and Computation - 10th International Symposium, ISAAC 1999, Proceedings. Springer Verlag. 1999. p. 269-278. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-46632-0_28

Bose, Prosenjit ; Kaklamanis, Christos ; Kirousis, Lefteris M. et al. / Station layouts in the presence of location constraints. Algorithms and Computation - 10th International Symposium, ISAAC 1999, Proceedings. editor / C. Pandu Rangan ; Alok Aggarwal. Springer Verlag, 1999. pp. 269-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9335d70fbcda4a82b68402c806419a7e,

title = "Station layouts in the presence of location constraints",

abstract = "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.",

author = "Prosenjit Bose and Christos Kaklamanis and Kirousis, {Lefteris M.} and Evangelos Kranakis and Danny Krizanc and David Peleg",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 10th Annual International Symposium on Algorithms and Computation, ISAAC 1999 ; Conference date: 16-12-1999 Through 18-12-1999",

year = "1999",

doi = "10.1007/3-540-46632-0_28",

language = "English (US)",

isbn = "3540669167",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "269--278",

editor = "Rangan, {C. Pandu} and Alok Aggarwal",

booktitle = "Algorithms and Computation - 10th International Symposium, ISAAC 1999, Proceedings",

}

TY - GEN

T1 - Station layouts in the presence of location constraints

AU - Bose, Prosenjit

AU - Kaklamanis, Christos

AU - Kirousis, Lefteris M.

AU - Kranakis, Evangelos

AU - Krizanc, Danny

AU - Peleg, David

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84944322305&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944322305&partnerID=8YFLogxK

U2 - 10.1007/3-540-46632-0_28

DO - 10.1007/3-540-46632-0_28

M3 - Conference contribution

AN - SCOPUS:84944322305

SN - 3540669167

SN - 9783540669166

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 269

EP - 278

BT - Algorithms and Computation - 10th International Symposium, ISAAC 1999, Proceedings

A2 - Rangan, C. Pandu

A2 - Aggarwal, Alok

PB - Springer Verlag

T2 - 10th Annual International Symposium on Algorithms and Computation, ISAAC 1999

Y2 - 16 December 1999 through 18 December 1999

ER -

Station layouts in the presence of location constraints

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this