\[\textsf{Visualizing WSPDs and their applications}\]

Introduced by Callahan and Kosaraju back in 1995, the concept of well-separated pair decomposition (\(\textsf{WSPD}\)) has occupied a special significance in computational geometry when it comes to solving distance problems in \(d\)-space. We present an in-browser tool that can be used to visualize \(\textsf{WSPD}\)s and several of their applications in \(2\)-space. Apart from research, it can also be used by instructors for introducing \(\textsf{WSPD}\)s in a classroom setting.

\(\textbf{Definition.}\) Let \(P\) and \(Q\) be two finite pointsets in \(d\)-space and \(s\) be a positive real number. We say that \(P\) and \(Q\) are \(\textbf{well-separated}\) with respect to \(s\), if there exist two congruent disjoint balls \(B_P\) and \(B_Q\), such that \(B_P\) contains the bounding-box of \(P\), \(B_Q\) contains the bounding-box of \(Q\), and the distance between \(B_P\) and \(B_Q\) is at least \(s\) times the common radius of \(B_P\) and \(B_Q\). The quantity \(s\) is referred to as the \(\textbf{separation ratio}\) of the decomposition. Using this idea of well-separability, one can define a well-separated decomposition (\(\textsf{WSPD}\)) of a pointset in the following way.

Let \(P\) be a set of \(n\) points in \(d\)-space and \(s\) be a positive real number. A \(\textbf{well-separated decomposition}\) for \(P\) with respect to \(s\) is a collection of pairs of non-empty subsets of \(P\), \(\{A_1,B_1\},\{A_2,B_2\},\ldots,\{A_m,B_m\}\) for some integer \(m\) (referred to as the size of the \(\textsf{WSPD}\)) such that

\[\textsf{Algorithms implemented}\]

We have implemented the following algorithms. For their pseudocodes, refer to the book on geometric spanners by Smid and Narasimhan (2007) and our paper that appeared in the proceedings of SoCG 2022 Multimedia.

\[\textsf{Using this tool}\]

There are primarily two steps for using this tool, (i) entering the points, (ii) selecting an algorithm.

\(\textsf{(i) Entering and deleting points}\)

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 points}\). 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. We have supplied a few built-in pointsets for experiments which can be easily selected using the drop-down menu.

Deletion of a point can be easily done just by right-clicking on the point.

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.

\(\textsf{(ii) Selecting an algorithm}\)

Once the desired point set is entered and finalized, the user can choose an algorithm for visualization. The slider bar can be used to control the animation speed. Algorithm tracing can be turned off using the \(\textsf{Highlight pseudocode steps}\) checkbox to increase animation speed. If the user is not interested to see the \(\textsf{WSPD}\) construction steps, it can be easily turned off using the \(\textsf{Animate WSPD steps}\) checkbox provided.

\(\textsf{(iii) Exporting the board as PNG/SVG}\)

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.

\(\textsf{(iv) Demonstration video}\)


\[\textsf{Reference}\]

Giri Narasimhan and Michiel Smid. Geometric spanner networks. Cambridge University Press, 2007.

\[\textsf{The developer team}\]

\[\textsf{Acknowledgments}\]

\(\textbf{Last edited: Thu May 5 10:32:30 EDT 2022 }\)