Back to search

University of North Florida. School of Computing

Fast-sparse-spanner: A practical algorithm for constructing low-stretch sparse geometric graphs

Abstract

dc:description.abstract

When constructing geometric graphs (vertices are points and edges are line segments connecting point pairs) on pointsets, stretch-factor (worst-case detour between any point pair) is often considered a quality metric. A low stretch-factor (a quantity that is usually > 1) guarantees short paths between all vertex pairs. A geometric graph having a stretch-factor of t is known as a t-spanner. Creating low stretch-factor geometric graphs for large pointsets with a low number of edges is an open problem in computational geometry. In this work, we have designed and engineered a new simple and practical (fast and memory-efficient) algorithm named Fast-Sparse-Spanner algorithm for constructing sparse low stretch-factor geometric graphs on large pointsets in the plane. To the best of current knowledge, this is the first practical algorithm capable of constructing fast low stretch-factor graphs on large pointsets with averagedegrees (hence, the number of edges) competitive with that of greedy-spanners, the sparsest known class of Euclidean geometric spanners. To evaluate the implementation in terms of computation speed, memory usage, and quality of output, extensive experiments were performed with synthetic and real-world pointsets, comparing results to Bucketing, the fastest known greedy spanner algorithm for pointsets in the plane, devised by Alewijnse et al. (Algorithmica, 2017). An experiment constructing a 1.1-spanner on a large synthetic pointset with 128K points uniformly distributed within a square demonstrated more than a 41-fold speedup, using roughly a third of the memory of Bucketing, with only a 3% increase in the average-degree of the resulting graph. When run on a pointset with a million points from the same distribution, a 130-fold speedup was observed, with roughly a fourth of the memory usage, and just a 6% increase in average-degree. In terms of diameter, the graphs generated by FastSparse-Spanner outperform greedy-spanners in most cases, exhibiting substantially lower diameter while maintaining near-greedy average-degree. Furthermore, the algorithm can be easily parallelized to take advantage of parallel environments. As a byproduct of this research, Fast-Stretch-Factor was designed and engineered as a practical parallelizable algorithm to measure the stretch-factor of any graph generated by Fast-Sparse-Spanner. Experiments demonstrated that it is significantly faster than the naive Dijkstra-based stretch-factor measurement algorithm. For broader uses and reproducibility of the results obtained, we have shared our code at https://github.com/ghoshanirban/FSS

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
  • Shariful, FNU
  • Shariful, FNU, 1993-
Advisors dc:contributor.advisor
  • Ghosh, Anirban
  • Dutta, Ayan
  • Kahanda, Indika
Contributors dc:contributor
  • Dr. Anirban Ghosh
  • Dr. Ayan Dutta
  • Dr. Indika Kahanda

Subjects

dc:subject × 16

Rights

dc:rights

Identifiers

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

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

Shariful, FNU; Shariful, FNU, 1993-. Fast-sparse-spanner: A practical algorithm for constructing low-stretch sparse geometric graphs. University of North Florida. School of Computing, https://digitalcommons.unf.edu/etd/1318