ghoshanirban/geometric-spanners

Abstract

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

1. About The Project
   • Built With
2. Getting Started
   • Prerequisites
   • Installation
3. Usage
4. Roadmap
5. Contributing
6. License
7. Contact
8. Acknowledgments

Built With

• GCC
• C++17
• CGAL
• Boost
• GMP
• MPFR

(back to top)

Getting Started

Prerequisites

Ensure the dependencies listed above are available.

Additionally, texlive-full is required for visualizations

Installation

1. Clone the repo

   git clone https://github.com/mgatc/geometric-spanners.git

2. Attempt to build

   cmake --build ./geometric-spanners/cmake-build-debug --target spanners

3. If unsuccessful, try configuring CMakeLists.txt to find the dependencies.

(back to top)

Usage

• ./spanners to view a brief usage summary

Viewing visualizations

• ./spanners [n] to produce a visualization of the algorithm configured in src/Scratch.h with n points
• ./spanners [filename.xy] to produce a visualization of the algorithm configured in src/Scratch.h with the points contained in filename.xy (the file extension must be .xy)

Running experiments

• ./spanners [filename.xml] [r] to run an experiment on real-world point sets defined in filename.xml with r iterations
• ./spanners [r] [start n] [end n] [increment] to run an experiment on eight synthetic distributions with r iterations

(back to top)

License

Distributed under the MIT License. See LICENSE.txt for more information.

(back to top)

Acknowledgments

• David Wisnosky
• Lucas Mougeot
• Anirban Ghosh
• Fred Anderson

(back to top)