Creator:
Hill, Darryl Richard
Date:
2015
Abstract:
Given a set of points P, we calculate the Delaunay triangulation of P, labeled DT(P). We describe an algorithm that selects a subset of edges from DT(P) to form the graph D8(P). We then prove that D8(P) has a constant spanning ratio of approximately 4.414 with respect to the complete graph, and a maximum degree of 8.
Subject:
Computer Science
Language:
English
Publisher:
Carleton University
Identifier:
Thesis Degree Name:
Master of Computer Science:
M.C.S.
Thesis Degree Level:
Master's
Thesis Degree Discipline:
Computer Science
Parent Collection:
Theses and Dissertations