Plane Spanners of Degree Eight
Public Deposited- Resource Type
- Creator
- 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
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
Copyright © 2015 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.
- Date Created
- 2015
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
hill-planespannersofdegreeeight.pdf | 2023-05-04 | Public | Download |