Beacon-based algorithms for geometric routing

Michael Biro; Justin Iwerks; Irina Kostitsyna; Joseph S.B. Mitchell

doi:10.1007/978-3-642-40104-6_14

Beacon-based algorithms for geometric routing

Michael Biro
, Justin Iwerks
, Irina Kostitsyna
, Joseph S.B. Mitchell

Applied Mathematics and Statistics

Stony Brook University

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

19 Scopus citations

Abstract

We consider beacons, an analog of geographical greedy routing, motivated by sensor network applications. A beacon b is a point object that can be activated to create a 'magnetic pull' towards itself everywhere in a polygonal domain P. We explore the properties of beacons and their effect on points in polygons, as well as demonstrate polynomial-time algorithms to compute a variety of structures defined by the action of beacons on P. We establish a polynomial-time algorithm for routing from a point s to a point t using a discrete set of candidate beacons, as well as a 2-approximation and a PTAS for routing between beacons placed without restriction in P.

Original language	English
Title of host publication	Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings
Pages	158-169
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-40104-6_14
State	Published - 2013
Event	13th International Symposium on Algorithms and Data Structures, WADS 2013 - London, ON, Canada Duration: Aug 12 2013 → Aug 14 2013

Publication series

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

Conference

Conference	13th International Symposium on Algorithms and Data Structures, WADS 2013
Country/Territory	Canada
City	London, ON
Period	08/12/13 → 08/14/13

Access to Document

10.1007/978-3-642-40104-6_14

Cite this

Biro, M., Iwerks, J., Kostitsyna, I., & Mitchell, J. S. B. (2013). Beacon-based algorithms for geometric routing. In Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings (pp. 158-169). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8037 LNCS). https://doi.org/10.1007/978-3-642-40104-6_14

@inproceedings{038158fbd4364484b52465d81f74169c,

title = "Beacon-based algorithms for geometric routing",

abstract = "We consider beacons, an analog of geographical greedy routing, motivated by sensor network applications. A beacon b is a point object that can be activated to create a 'magnetic pull' towards itself everywhere in a polygonal domain P. We explore the properties of beacons and their effect on points in polygons, as well as demonstrate polynomial-time algorithms to compute a variety of structures defined by the action of beacons on P. We establish a polynomial-time algorithm for routing from a point s to a point t using a discrete set of candidate beacons, as well as a 2-approximation and a PTAS for routing between beacons placed without restriction in P.",

author = "Michael Biro and Justin Iwerks and Irina Kostitsyna and Mitchell, \{Joseph S.B.\}",

year = "2013",

doi = "10.1007/978-3-642-40104-6\_14",

language = "English",

isbn = "9783642401039",

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

pages = "158--169",

booktitle = "Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings",

note = "13th International Symposium on Algorithms and Data Structures, WADS 2013 ; Conference date: 12-08-2013 Through 14-08-2013",

}

Biro, M, Iwerks, J, Kostitsyna, I & Mitchell, JSB 2013, Beacon-based algorithms for geometric routing. in Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8037 LNCS, pp. 158-169, 13th International Symposium on Algorithms and Data Structures, WADS 2013, London, ON, Canada, 08/12/13. https://doi.org/10.1007/978-3-642-40104-6_14

Beacon-based algorithms for geometric routing. / Biro, Michael; Iwerks, Justin; Kostitsyna, Irina et al.
Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. 2013. p. 158-169 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8037 LNCS).

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

TY - GEN

T1 - Beacon-based algorithms for geometric routing

AU - Biro, Michael

AU - Iwerks, Justin

AU - Kostitsyna, Irina

AU - Mitchell, Joseph S.B.

PY - 2013

Y1 - 2013

N2 - We consider beacons, an analog of geographical greedy routing, motivated by sensor network applications. A beacon b is a point object that can be activated to create a 'magnetic pull' towards itself everywhere in a polygonal domain P. We explore the properties of beacons and their effect on points in polygons, as well as demonstrate polynomial-time algorithms to compute a variety of structures defined by the action of beacons on P. We establish a polynomial-time algorithm for routing from a point s to a point t using a discrete set of candidate beacons, as well as a 2-approximation and a PTAS for routing between beacons placed without restriction in P.

AB - We consider beacons, an analog of geographical greedy routing, motivated by sensor network applications. A beacon b is a point object that can be activated to create a 'magnetic pull' towards itself everywhere in a polygonal domain P. We explore the properties of beacons and their effect on points in polygons, as well as demonstrate polynomial-time algorithms to compute a variety of structures defined by the action of beacons on P. We establish a polynomial-time algorithm for routing from a point s to a point t using a discrete set of candidate beacons, as well as a 2-approximation and a PTAS for routing between beacons placed without restriction in P.

UR - https://www.scopus.com/pages/publications/84881190611

U2 - 10.1007/978-3-642-40104-6_14

DO - 10.1007/978-3-642-40104-6_14

M3 - Conference contribution

AN - SCOPUS:84881190611

SN - 9783642401039

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

SP - 158

EP - 169

BT - Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings

T2 - 13th International Symposium on Algorithms and Data Structures, WADS 2013

Y2 - 12 August 2013 through 14 August 2013

ER -

Biro M, Iwerks J, Kostitsyna I, Mitchell JSB. Beacon-based algorithms for geometric routing. In Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. 2013. p. 158-169. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40104-6_14

Beacon-based algorithms for geometric routing

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this