Establishing strong connectivity using optimal radius half-disk antennas

AuthorSearch for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for:
TypeArticle
Proceedings titleProceedings of the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
Conference23rd Annual Canadian Conference on Computational Geometry, CCCG 2011, 10 August 2011 through 12 August 2011, Toronto, ON
SubjectAperture angle; Communication graphs; Directional Antenna; Euclidean minimum spanning trees; Optimal radius; Strong connectivity; Strongly connected; Wireless devices; Directive antennas; Optimization; Computational geometry
AbstractGiven a set S of points in the plane representing wireless devices, each point equipped with a directional antenna of radius r and aperture angle α ≥ 180°, our goal is to find orientations and a minimum r for these antennas such that the induced communication graph is strongly connected. We show that r = √ 3 suffices to establish strong connectivity, assuming that the longest edge in the Euclidean minimum spanning tree for S is 1. This result is optimal in the sense that r = √ 3 is necessary in the worst-case for α ∈ [180°; 240°). In contrast, r = 2 is sometimes necessary when α < 180°.
Publication date
LanguageEnglish
AffiliationNational Research Council Canada (NRC-CNRC); NRC Institute for Information Technology (IIT-ITI)
Peer reviewedYes
NPARC number21271114
Export citationExport as RIS
Report a correctionReport a correction
Record identifier684304f8-5b55-4a87-afaa-bdd5ac04c341
Record created2014-03-24
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)