Combinatorics of beacon-based routing and coverage

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

Research output: Contribution to conferencePaperpeer-review

11 Scopus citations

Abstract

We consider combinatorial problems motivated by sensor networks for beacon-based point-to-point routing and covering. A beacon b is a point that can be activated to effect a 'magnetic pull' toward itself everywhere in a polygonal domain P. The routing problem asks how many beacons are required to route between any pair of points in a polygonal domain P. In simple polygons with n vertices we show that [n/2 ] -1 beacons are sometimes necessary and always sufficient. In polygons with n holes, we establish that [n/2 ] -h-1 beacons are sometimes necessary while [n/2 ] + h - 1 beacons are always sufficient. Loose bounds for simple orthogonal polygons are also shown. We consider art gallery problems where beacons function as guards. Loose bounds are given for covering simple polygons, polygons with holes and simple orthogonal polygons.

Original languageEnglish (US)
Pages129-134
Number of pages6
StatePublished - 2013
Externally publishedYes
Event25th Canadian Conference on Computational Geometry, CCCG 2013 - Waterloo, Canada
Duration: Aug 8 2013Aug 10 2013

Conference

Conference25th Canadian Conference on Computational Geometry, CCCG 2013
Country/TerritoryCanada
CityWaterloo
Period8/8/138/10/13

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Combinatorics of beacon-based routing and coverage'. Together they form a unique fingerprint.

Cite this