Document Open Access Logo

An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners (Media Exposition)

Authors Fred Anderson, Anirban Ghosh , Matthew Graham, Lucas Mougeot, David Wisnosky

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.61.pdf
  • Filesize: 0.62 MB
  • 4 pages

Document Identifiers

Author Details

Fred Anderson
  • School of Computing, University of North Florida, Jacksonville, FL, USA
Anirban Ghosh
  • School of Computing, University of North Florida, Jacksonville, FL, USA
Matthew Graham
  • School of Computing, University of North Florida, Jacksonville, FL, USA
Lucas Mougeot
  • School of Computing, University of North Florida, Jacksonville, FL, USA
David Wisnosky
  • School of Computing, University of North Florida, Jacksonville, FL, USA

Funding

Research on this paper is supported by the NSF Award CCF-1947887 and by the University of North Florida Academic Technology Grant.

Cite As Get BibTex

Fred Anderson, Anirban Ghosh, Matthew Graham, Lucas Mougeot, and David Wisnosky. An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners (Media Exposition). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 61:1-61:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SoCG.2021.61

Abstract

The construction of bounded-degree plane geometric spanners has been a focus of interest in the field of geometric spanners for a long time. To date, several algorithms have been designed with various trade-offs in degree and stretch factor. Using JSXGraph, a state-of-the-art JavaScript library for geometry, we have implemented seven of these sophisticated algorithms so that they can be used for further research and teaching computational geometry. We believe that our interactive tool can be used by researchers from related fields to understand and apply the algorithms in their research. Our tool can be run in any modern browser. The tool will be permanently maintained by the second author at https://ghoshanirban.github.io/bounded-degree-plane-spanners/index.html

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
Keywords
  • graph approximation
  • Delaunay triangulations
  • geometric spanners
  • plane spanners
  • bounded-degree spanners

Metrics

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

Supplementary Materials

References

  1. Ahmad Biniaz. Plane hop spanners for unit disk graphs: Simpler and better. Comput. Geom., 89:101622, 2020. URL: https://doi.org/10.1016/j.comgeo.2020.101622.
  2. Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari, and Michiel Smid. Towards plane spanners of degree 3. Journal of Computational Geometry, 8(1):11-31, 2017. Google Scholar
  3. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perković. Plane spanners of maximum degree six. In International Colloquium on Automata, Languages, and Programming, pages 19-30. Springer, 2010. Google Scholar
  4. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perković. The stretch factor of l₁-and l_∞-delaunay triangulations. In European Symposium on Algorithms, pages 205-216. Springer, 2012. Google Scholar
  5. Nicolas Bonichon, Iyad Kanj, Ljubomir Perković, and Ge Xia. There are plane spanners of degree 4 and moderate stretch factor. Discrete & Computational Geometry, 53(3):514-546, 2015. Google Scholar
  6. Prosenjit Bose, Paz Carmi, and Lilach Chaitman-Yerushalmi. On bounded degree plane strong geometric spanners. Journal of Discrete Algorithms, 15:16-31, 2012. Google Scholar
  7. Prosenjit Bose, Joachim Gudmundsson, and Michiel Smid. Constructing plane spanners of bounded degree and low weight. Algorithmica, 42(3-4):249-264, 2005. Google Scholar
  8. Prosenjit Bose, Darryl Hill, and Michiel Smid. Improved spanning ratio for low degree plane spanners. Algorithmica, 80(3):935-976, 2018. Google Scholar
  9. Prosenjit Bose and Michiel Smid. On plane geometric spanners: A survey and open problems. Computational Geometry, 46(7):818-830, 2013. Google Scholar
  10. Prosenjit Bose, Michiel Smid, and Daming Xu. Delaunay and diamond triangulations contain spanners of bounded degree. International Journal of Computational Geometry & Applications, 19(02):119-140, 2009. Google Scholar
  11. Nicolas Catusse, Victor Chepoi, and Yann Vaxès. Planar hop spanners for unit disk graphs. In International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pages 16-30. Springer, 2010. Google Scholar
  12. L Paul Chew. There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences, 39(2):205-219, 1989. Google Scholar
  13. LP Chew. There is a planar graph almost as good as the complete graph, 2nd symp. on computational geometry, 1986. Google Scholar
  14. Gautam Das and Paul J Heffernan. Constructing degree-3 spanners with other sparseness properties. International Journal of Foundations of Computer Science, 7(02):121-135, 1996. Google Scholar
  15. Adrian Dumitrescu and Anirban Ghosh. Lattice spanners of low degree. Discrete Mathematics, Algorithms and Applications, 8(03):1650051, 2016. Google Scholar
  16. Adrian Dumitrescu and Anirban Ghosh. Lower bounds on the dilation of plane spanners. International Journal of Computational Geometry & Applications, 26(02):89-110, 2016. Google Scholar
  17. Adrian Dumitrescu, Anirban Ghosh, and Csaba D Tóth. Sparse hop spanners for unit disk graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  18. Mohammad Farshi and Seyed Hossein Hosseini. Visualization of geometric spanner algorithms. In 32nd International Symposium on Computational Geometry (SoCG 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  19. Iyad Kanj, Ljubomir Perkovic, and Duru Türkoǧlu. Degree four plane spanners: Simpler and better. Journal of Computational Geometry, 8(2):3-31, 2017. Google Scholar
  20. Iyad A Kanj, Ljubomir Perković, and Ge Xia. On spanners and lightweight spanners of geometric graphs. SIAM Journal on Computing, 39(6):2132-2161, 2010. Google Scholar
  21. Rolf Klein, Martin Kutz, and Rainer Penninger. Most finite point sets in the plane have dilation > 1. Discrete & Computational Geometry, 53(1):80-106, 2015. Google Scholar
  22. Xiang-Yang Li and Yu Wang. Efficient construction of low weighted bounded degree planar spanner. International Journal of Computational Geometry & Applications, 14(01n02):69-84, 2004. Google Scholar
  23. Wolfgang Mulzer. Minimum dilation triangulations for the regular n-gon. Master’s thesis, Freie Universität Berlin, Germany, 2004. Google Scholar
  24. Giri Narasimhan and Michiel Smid. Geometric spanner networks. Cambridge University Press, 2007. Google Scholar
  25. Ljubomir Perkovic and Iyad A Kanj. On geometric spanners of euclidean and unit disk graphs. In 25th International Symposium on Theoretical Aspects of Computer Science. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2008. Google Scholar
  26. Csaba D Toth, Joseph O'Rourke, and Jacob E Goodman. Handbook of discrete and computational geometry. Chapman and Hall/CRC, 2017. Google Scholar
  27. Ge Xia. The stretch factor of the delaunay triangulation is less than 1.998. SIAM Journal on Computing, 42(4):1620-1659, 2013. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact