The construction of bounded-degree plane geometric spanners has been 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 \(\textsf{JSXGraph}\), a state-of-the-art JavaScript library for geometry, we have implemented seven of these sophisticated algorithms (see below) so that they can be used for research in geometric spanners and teaching computational geometry. Our interactive tool can also be used by researchers from related fields to easily understand and apply these fascinating algorithms in their research. This tool can run on any modern-day browser. However, for the best possible rendering, we recommend using a Chromium-based browser such as Google Chrome.
There are primarily two steps for using this tool, (i) entering the points, (ii) selecting an algorithm for spanner construction.
It is assumed that all the points do not lie on the same straight-line. The tool supports three ways to enter points onto the canvas. The user can use a combination of these three to create a point set for experiments. Among these, the easiest is to just click on the canvas. In this case, the points will be plotted automatically. The second way is to manually enter the points inside the text-box and hit \(\textsf{PLOT}\). The third way is to use randomly generated point sets. If the desired cardinality of a point set is entered in the textbox above the \(\textsf{GENERATE}\) button, the tool can quickly generate a point set and plot the points on the canvas when the \(\textsf{GENERATE}\) button is hit.
The coordinates of the plotted points are always shown in the text-box. These coordinates can be easily manipulated by the user. If the coordinates of at least one point is manipulated inside the text-box, the \(\textsf{PLOT}\) button should be hit to see the changes reflected on the board.
Deletion of a point can be easily done just by right-clicking on the point.
For convenience, the tool comes with five built-in point sets for performing experiments with the algorithms; see the table next.
\[ \small{ \begin{array}{|c|c|} \hline \textsf{Point set} & \textsf{Number of points }\\ \hline \hline \text{The example from the paper BGS2005[1]} & 18 \\ \hline \text{Top 12 U.S. Cities by Population} & 12 \\ \hline \text{U.S. Cities with Population > 100K} & 317 \\ \hline \text{100-point Circle} & 100 \\ \hline \text{Archimedes Spiral} & 100 \\ \hline \end{array} } \]Every point is automatically given an integer ID for easy reference on the board. However, the user can turn off this feature by unchecking the \(\textsf{Show point IDs}\) checkbox.
A useful feature of this tool is that it auto-zooms on the input point set for easier verification of the point set and the generated spanner. The user can also zoom-in/out manually by clicking on the \(\textsf{+}\) and \(\textsf{-}\) buttons at the bottom of the board.
Once the desired point set is entered and finalized, click the \(\textsf{NEXT}\) button at the bottom. Now one can see a menu of the implemented algorithms to choose from. For reference, we have included a \(\textsf{URL TO THE PAPER}\) button that can take the user to the source paper using its doi.
Some of the implemented algorithms need an additonal parameter value for execution. The user can choose the desired parameter value(s) using a slider. We encourage the user to refer to the source paper in order to understand these parameters. Furthermore, for these algorithms, the user can optionally select a step from the selected algorithm for viewing the intermediate results.
Once the algorithm is selected, hitting the \(\textsf{GO}\) button will construct the spanner and draw it on the board. The spanner edges are shown in a textbox for further use. Every edge in this box is represented using a pair of integers \(i~~j\) where \(i,j \in \{0,1,\ldots,n-1\}\). Additionally, the tool also displays various properties of the generated spanner such as the number of vertices, number of edges, exact stretch factor, exact degree, average degree, and lightness (ratio of the weight of the generated spanner to that of the Euclidean minimum spanning tree on the point set).
Since these algorithms use edges from a \(L_2\)-Delaunay triangulation of the input point set, we show the Delaunay edges in gray. These edges remain visible even after the spanner is constructed. The \(\textsf{Show Delaunay Edges}\) checkbox can be used to disable the Delaunay edges from the board.
The user can add/delete points on this page by clicking on \(\textsf{EDIT POINTS}\). This will take the user to the page where new points can be added or deleted.
The tool allows users to export an image of the board (not necessarily with the spanner) in PNG and SVG formats. To capture an image, simply click either on the \(\textsf{PNG}\) or on the \(\textsf{SVG}\) button.
The following table lists the implemented algorithms, sorted by the degree they guarantee. The best known upper bound of \(1.998\) for the stretch factor of the \(L_2\)-Delaunay triangulation is used in this table for expressing the stretch factors. For ease of reference, we have abbreviated the implemented algorithms using their author names and year of publication.
\[ \small{ \begin{array}{|c|c|c|} \hline \textsf{Reference} & \textsf{Degree} & \textsf{Upper bound on stretch factor }\\ \hline \hline \text{ Bose, Gudmundsson, and Smid }\text{(BGS2005)[1]} & 27 & 1.998(\pi+1)\approx 8.3 \\ \hline \text{ Li and Wang } \text{(LW2004)[2]}& 23 & 1.998(1 + \frac{\pi}{\sqrt{2}})\approx 6.4 \\ \hline \text{ Bose, Smid, and Xu }\text{(BSX2009)[3]} & 17 & 1.998(2+2\sqrt{3}+\frac{3\pi}{2} + 2\pi \sin \frac{\pi}{12}) \approx 23.6 \\ \hline \text{ Kanj, Perkovic, and Xia }\text{(KPX2010)[4]} & 14 & 1.998 (1 + \frac{2\pi}{14 \cos (\pi/14)})\approx 2.9 \\ \hline \text{Bose, Hill, and Smid }\text{(BHS2017)[5]} & 8 & 1.998 \left( 1 + \frac{2\pi}{6 \cos (\pi/6) } \right) \approx 4.4 \\ \hline \text{ Bose, Carmi, and Chaitman-Yerushalmi }\text{(BCC2012)[6]} & 7 & 1.998 (1 + \sqrt{2})^2 \approx 11.6 \\ \hline \text{ Bose, Carmi, and Chaitman-Yerushalmi }\text{(BCC2012)[6]} & 6 & 1.998 \left(\frac{1}{1-\tan (\pi/7)(1 + 1/\cos (\pi/14))} \right)\approx 81.7 \\ \hline \end{array} } \]\(\textsf{Last edited: Wed 24 Mar 2021 17:54:33 PM EST}\)