Back to search

University of British Columbia

On path-greedy geometric spanners

Abstract

dc:description

A t-spanner is a graph in which the shortest path between two vertices never exceeds t times the distance between the two nodes – a t-approximation of the complete graph. A geometric graph is one in which its vertices are points with defined coordinates and the edges correspond to line segments between them with a distance function, such as Euclidean distance. Geometric spanners are used to design networks of reduced complexity, optimizing metrics such as the planarity or degree of the graph. One famous algorithm used to generate spanners is path-greedy, which scans pairs of points in non-decreasing order of distance and adds the edge between them unless the current set of added edges already connects them with a path that t-approximates the edge length. Graphs from this algorithm are called path-greedy spanners. This work analyzes properties of path-greedy geometric spanners under different conditions. Specifically, we answer an open problem regarding the planarity and degree of path-greedy 5.19-spanners in convex point sets, and explore how the algorithm behaves under random tiebreaks for grid point sets. Lastly, we show a simple and efficient way to reduce the degree of a plane spanner by adding extra points.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Morais de Arruda Siaudzionis, Lucca
Contributors dc:contributor
  • Evans, William

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/79736

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Morais de Arruda Siaudzionis, Lucca. On path-greedy geometric spanners. master's thesis, University of British Columbia, 2021. http://hdl.handle.net/2429/79736