Implementation of Minimum Edge Constraints Sets for Proximity Graphs

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: 

Duong, Edward

Date: 

2018

Abstract: 

For certain edge-constrained proximity algorithms, not every edge of the resulting graph needs to be explicitly stored. This has implications for graph compression. We examine the application and runtime performance on minimum edge-constrained algorithms for three proximity graph types: Delaunay triangulation, Gabriel graph and minimum spanning tree.

Implementation details on these algorithms are given, their performance in both large real world datasets and randomized datasets are evaluated. In addition, their compression metrics, the number of edges that are reduced from the constraint edge set, are investigated.

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).