Bounded-Angle Minimum Spanning Trees

Authors Ahmad Biniaz, Prosenjit Bose, Anna Lubiw, Anil Maheshwari



PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.14.pdf
  • Filesize: 1.02 MB
  • 22 pages

Document Identifiers

Author Details

Ahmad Biniaz
  • School of Computer Science, University of Windsor, Canada
Prosenjit Bose
  • School of Computer Science, Carleton University, Ottawa, Canada
Anna Lubiw
  • Cheriton School of Computer Science, University of Waterloo, Canada
Anil Maheshwari
  • School of Computer Science, Carleton University, Ottawa, Canada

Acknowledgements

Matthew Katz’s invited talk on bounded-angle spanning tree problems at CCCG 2018 was the inspiration for this work. We thank Therese Biedl for helpful discussions.

Cite AsGet BibTex

Ahmad Biniaz, Prosenjit Bose, Anna Lubiw, and Anil Maheshwari. Bounded-Angle Minimum Spanning Trees. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SWAT.2020.14

Abstract

Motivated by the connectivity problem in wireless networks with directional antennas, we study bounded-angle spanning trees. Let P be a set of points in the plane and let α be an angle. An α-ST of P is a spanning tree of the complete Euclidean graph on P with the property that all edges incident to each point p ∈ P lie in a wedge of angle α centered at p. We study the following closely related problems for α = 120 degrees (however, our approximation ratios hold for any α ⩾ 120 degrees). 1) The α-minimum spanning tree problem asks for an α-ST of minimum sum of edge lengths. Among many interesting results, Aschner and Katz (ICALP 2014) proved the NP-hardness of this problem and presented a 6-approximation algorithm. Their algorithm finds an α-ST of length at most 6 times the length of the minimum spanning tree (MST). By adopting a somewhat similar approach and using different proof techniques we improve this ratio to 16/3. 2) To examine what is possible with non-uniform wedge angles, we define an ̅α-ST to be a spanning tree with the property that incident edges to all points lie in wedges of average angle α. We present an algorithm to find an ̅α-ST whose largest edge-length and sum of edge lengths are at most 2 and 1.5 times (respectively) those of the MST. These ratios are better than any achievable when all wedges have angle α. Our algorithm runs in linear time after computing the MST.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Approximation algorithms analysis
Keywords
  • bounded-angle MST
  • directional antenna
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Eyal Ackerman, Tsachik Gelander, and Rom Pinchasi. Ice-creams and wedge graphs. Computational Geometry: Theory and Applications, 46(3):213-218, 2013. Google Scholar
  2. Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Clemens Huemer, Attila Pór, Francisco Santos, Bettina Speckmann, and Birgit Vogtenhuber. Maximizing maximal angles for plane straight-line graphs. Computational Geometry: Theory and Applications, 46(1):17-28, 2013. Also in WADS'07. Google Scholar
  3. Sanjeev Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5):753-782, 1998. Google Scholar
  4. Rom Aschner and Matthew J. Katz. Bounded-angle spanning tree: Modeling networks with angular constraints. Algorithmica, 77(2):349-373, 2017. Also in ICALP'14. Google Scholar
  5. Rom Aschner, Matthew J. Katz, and Gila Morgenstern. Do directional antennas facilitate in reducing interferences? In Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 201-212, 2012. Google Scholar
  6. Ahmad Biniaz. Euclidean bottleneck bounded-degree spanning tree ratios. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020. Google Scholar
  7. Ahmad Biniaz, Anil Maheshwari, and Michiel Smid. Flip distance to some plane configurations. Computational Geometry: Theory and Applications, 81:12-21, 2019. Also in SWAT'18. Google Scholar
  8. Prosenjit Bose, Paz Carmi, Mirela Damian, Robin Y. Flatland, Matthew J. Katz, and Anil Maheshwari. Switching to directional antennas with constant increase in radius and hop distance. Algorithmica, 69(2):397-409, 2014. Also in WADS'11. Google Scholar
  9. Prosenjit Bose, Leonidas J. Guibas, Anna Lubiw, Mark H. Overmars, Diane L. Souvaine, and Jorge Urrutia. The floodlight problem. International Journal of Computational Geometry & Applications, 7(1/2):153-163, 1997. Also in CCCG'93. Google Scholar
  10. Paolo M. Camerini. The min-max spanning tree problem and some extensions. Information Processing Letters, 7(1):10-14, 1978. Google Scholar
  11. Ioannis Caragiannis, Christos Kaklamanis, Evangelos Kranakis, Danny Krizanc, and Andreas Wiese. Communication in wireless networks with directional antennas. In Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 344-351, 2008. Google Scholar
  12. Paz Carmi, Matthew J. Katz, Zvi Lotker, and Adi Rosén. Connectivity guarantees for wireless networks with directional antennas. Computational Geometry: Theory and Applications, 44(9):477-485, 2011. Google Scholar
  13. Timothy M. Chan. Euclidean bounded-degree spanning tree ratios. Discrete & Computational Geometry, 32(2):177-194, 2004. Also in SoCG'03. Google Scholar
  14. Mirela Damian and Robin Y. Flatland. Spanning properties of graphs induced by directional antennas. Discrete Mathematics, Algorithms and Applications, 5(3), 2013. Google Scholar
  15. Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Jaroslav Opatrny, Oscar Morales Ponce, and Ladislav Stacho. Strong connectivity in sensor networks with given number of directional antennae of bounded angle. Discrete Mathematics, Algorithms and Applications, 4(3), 2012. Also in COCOA'10. Google Scholar
  16. Stefan Dobrev, Evangelos Kranakis, Oscar Morales Ponce, and Milan Plzík. Robust sensor range for constructing strongly connected spanning digraphs in UDGs. In Proceedings of the 7th International Computer Science Symposium in Russia (CSR), pages 112-124, 2012. Google Scholar
  17. Adrian Dumitrescu, János Pach, and Géza Tóth. Drawing Hamiltonian cycles with no large angles. Electronic Journal of Combinatorics, 19(2):P31, 2012. Also in GD'94. Google Scholar
  18. Sándor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, and Neal E. Young. A network-flow technique for finding low-weight bounded-degree spanning trees. Journal of Algorithms, 24(2):310-324, 1997. Also in IPCO 1996. Google Scholar
  19. Sándor P. Fekete and Gerhard J. Woeginger. Angle-restricted tours in the plane. Computational Geometry: Theory and Applications, 8:195-218, 1997. Google Scholar
  20. Magnús M. Halldórsson and Takeshi Tokuyama. Minimizing interference of a wireless ad-hoc network in a plane. Theoretical Computer Science, 402(1):29-42, 2008. Google Scholar
  21. Raja Jothi and Balaji Raghavachari. Degree-bounded minimum spanning trees. Discrete Applied Mathematics, 157(5):960-970, 2009. Google Scholar
  22. Matthew J. Katz. Personal communication. Google Scholar
  23. Samir Khuller, Balaji Raghavachari, and Neal E. Young. Low-degree spanning trees of small weight. SIAM Journal on Computing, 25(2):355-368, 1996. Also in STOC'94. Google Scholar
  24. Evangelos Kranakis, Fraser MacQuarrie, and Oscar Morales Ponce. Connectivity and stretch factor trade-offs in wireless sensor networks with directional antennae. Theoretical Computer Science, 590:55-72, 2015. Google Scholar
  25. Clyde L. Monma and Subhash Suri. Transitions in geometric minimum spanning trees. Discrete & Computational Geometry, 8:265-293, 1992. Also in SoCG'91. Google Scholar
  26. Jan van Leeuwen and Anneke A. Schoone. Untangling a travelling salesman tour in the plane. In Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG), pages 87-98, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail