Beacon-based algorithms for geometric routing

M Biro, J Iwerks, I Kostitsyna, JSB Mitchell - Algorithms and Data Structures …, 2013 - Springer
Algorithms and Data Structures: 13th International Symposium, WADS 2013 …, 2013Springer
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 …
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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果