Plane Spanners of Degree Eight

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

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

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

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).