Document Open Access Logo

Visualization of Geometric Spanner Algorithms

Authors Mohammad Farshi, Seyed Hossein Hosseini

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2016.67.pdf
  • Filesize: 405 kB
  • 4 pages

Document Identifiers

Subject Classification

Keywords
  • geometric spanner networks
  • geometric spanner algorithms animations.

Metrics

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

Abstract

It is  easier to understand an algorithm when it can be seen in interactive mode. The current study implemented four algorithms to construct geometric spanners; the path-greedy, gap-greedy, Theta-graph and Yao-graph algorithms. The data structure visualization framework (http://www.cs.usfca.edu/~galles/visualization/) developed by David Galles was used.    

Two features were added to allow its use in spanner algorithm visualization: support point-based algorithms and export of the output to Ipe drawing software format. The interactive animations in the framework make steps of visualization beautiful and  media controls are available to manage the animations. Visualization does not require extensions to be installed on the web browser. It is available at http://cs.yazd.ac.ir/cgalg/AlgsVis/.

Cite As Get BibTex

Mohammad Farshi and Seyed Hossein Hosseini. Visualization of Geometric Spanner Algorithms. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 67:1-67:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.67

Author Details

Mohammad Farshi
Seyed Hossein Hosseini

References

  1. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete &Computational Geometry, 9(1):81-100, 1993. Google Scholar
  2. Sunil Arya and Michiel Smid. Efficient construction of a bounded-degree spanner with low weight. Algorithmica, 17(1):33-54, 1997. Google Scholar
  3. Rom Aschner. Geometric spanners applet. http://www.cs.bgu.ac.il/~romas/greedy.html .
  4. Ken Clarkson. Approximation algorithms for shortest path motion planning. In Proc. of the 19t Annual ACM Symp. on Theory of Computing, pages 56-65. ACM, 1987. Google Scholar
  5. Mohammad Farshi and Seyed Hossein Hosseini. Geometric spanner algorithms visualizations. http://cs.yazd.ac.ir/cgalg/AlgsVis/ .
  6. David Galles. Data structure visualizations. http://www.cs.usfca.edu/~galles/visualization/ .
  7. Giri Narasimhan and Michiel Smid. Geometric spanner networks. Cambridge University Press, 2007. Google Scholar
  8. Daniel Russel and Leonidas J. Guibas. Exploring protein folding trajectories using geometric spanners. Pacific Symposium on Biocomputing, pages 40-51, 2005. Google Scholar
  9. Petra Specht and Michiel Smid. Visualization of spanners. http://isgwww.cs.uni-magdeburg.de/tspanner/spanner.html .
  10. Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721-736, 1982. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact