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


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)
Number of pages6
StatePublished - 2013
Externally publishedYes
Event25th Canadian Conference on Computational Geometry, CCCG 2013 - Waterloo, Canada
Duration: Aug 8 2013Aug 10 2013


Conference25th Canadian Conference on Computational Geometry, CCCG 2013

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Computational Mathematics


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

Cite this