The construction of bounded-degree plane geometric spanners has been a focus of interest since 2002 when Bose, Gudmundsson, and Smid proposed the first algorithm to construct such spanners. To date, eleven algorithms have been designed with various trade-offs in degree and stretch factor. We have carefully implemented these sophisticated algorithms in C++ using the CGAL library and experimented with them using large synthetic and real-world pointsets. Our experiments have revealed their practical behavior on large pointsets and their real-world efficacy. We share the implementations here for broader uses and future research.
We present a simple practical algorithm, named AppxStretchFactor, that can estimate stretch factors (obtains lower bounds on the exact stretch factors) of geometric spanners fast -- a challenging problem for which no practical algorithm is known yet. In our experiments with bounded-degree plane geometric spanners, we find that AppxStretchFactor estimates stretch factors almost precisely and gives linear runtime performance for the pointset distributions considered. We also found it to be much faster than the naive Dijkstra-based algorithm for calculating stretch factors. Further, it can be easily parallelized, making it very useful for estimating stretch factors of large spanners.
Table of Contents
Ensure the dependencies listed above are available.
Additionally, texlive-full is required for visualizations
- Clone the repo
git clone https://github.com/mgatc/geometric-spanners.git
- Attempt to build
cmake --build ./geometric-spanners/cmake-build-debug --target spanners
- If unsuccessful, try configuring
CMakeLists.txtto find the dependencies.
./spannersto view a brief usage summary
./spanners [n]to produce a visualization of the algorithm configured insrc/Scratch.hwithnpoints./spanners [filename.xy]to produce a visualization of the algorithm configured insrc/Scratch.hwith the points contained infilename.xy(the file extension must be.xy)
./spanners [filename.xml] [r]to run an experiment on real-world point sets defined infilename.xmlwithriterations./spanners [r] [start n] [end n] [increment]to run an experiment on eight synthetic distributions withriterations
Distributed under the MIT License. See LICENSE.txt for more information.