Back to search

Carleton University

Geometric Spanners For Compact Regions

Abstract

dc:description.abstract

Let R be a set of n pairwise disjoint compact path connected subsets of the plane. We refer to the elements of R as regions. We suppose that travelling inside each of these regions is free, whereas the cost of travelling outside these regions corresponds to the travelled distance. This gives rise to a metric space (R, delta(T)) where T corresponds to the most cost-effective graph connecting the regions of R and delta(T) corresponds to the length of a shortest path in T. We show that T can be approximated by two cone based algorithms: the first algorithm, based on Yao graphs, yields a graph whose spanning ratio is 1/(1-sin(theta/2) and the second, based on theta graphs, yields a graph whose spanning ratio is (1/(cos theta - sin theta. We also show that T can be approximated by a greedy algorithm when the regions are assumed to be "fat".

Degree

thesis:*
Name thesis:degree_name
Master of Computer Science (M.C.S.)
Level thesis:degree_level
Master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
Carleton University
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chaplain Corriveau, Francois-Xavier

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Copyright © 2021 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Carleton University
Base URL
carleton.scholaris.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chaplain Corriveau, Francois-Xavier. Geometric Spanners For Compact Regions. Master's thesis, Carleton University, 2021. https://hdl.handle.net/20.500.14718/41530