Back to search

University of North Florida. School of Computing

Bounded-degree Plane Geometric Spanners: Connecting the Dots Between Theory and Practice

Abstract

dc:description.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 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 (obtains lower bounds on the exact stretch factors) of geometric spanners – 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. Further, it gives linear runtime performance in practice for the pointset distributions considered in this work, making it much faster than the naive Dijkstra-based algorithm for calculating stretch factors.

Degree

thesis:*
Name thesis:degree_name
Master of Science in Computer and Information Sciences (MS)
Discipline thesis:degree_discipline
Computing
Grantor
University of North Florida. School of Computing
Date dc:date.issued
Spring

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Graham, Matthew Alexander
  • Graham, Matthew A., 1989-
Advisors dc:contributor.advisor
  • Ghosh, Anirban
  • Asaithambi, Asai
  • Dutta, Ayan
Contributors dc:contributor
  • Dr. Anirban Ghosh
  • Dr. Asai Asaithambi
  • Dr. Ayan Dutta

Subjects

dc:subject × 8

Rights

dc:rights

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.unf.edu/etd/1122

Chain of custody

source
Harvested from
University of North Florida
Base URL
digitalcommons.unf.edu/do/oai/
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Graham, Matthew Alexander; Graham, Matthew A., 1989-. Bounded-degree Plane Geometric Spanners: Connecting the Dots Between Theory and Practice. University of North Florida. School of Computing, https://digitalcommons.unf.edu/etd/1122