Computational Engineering Commons^™

Bounded-Degree Plane Geometric Spanners: Connecting The Dots Between Theory And Practice, Matthew Alexander Graham

UNF Graduate Theses and Dissertations

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 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 and real-world efficacy. We share the implementations via GitHub for broader uses and future research.

We present a simple practical algorithm, named AppxStretchFactor, that can estimate stretch factors …