Optimal Bichromatic Plane Spanning Trees For Special Point Sets
Public Deposited- Resource Type
- Creator
- Abstract
Given a point set S=RꓴB, where R is a set of red points and B is a set of blue points, we desire to find T*, a minimum weight spanning tree such that every edge has one red endpoint and one blue endpoint and no two edges cross. We call T* a bichromatic plane minimum spanning tree (MinBPST). We say a point set is semi-collinear when the blue points lie on a line and the red points lie on one side of the line. In this thesis, we present an O(|B|^3|R|^2) running time algorithm for finding T* on a set of semi-collinear points. We also discuss an implementation of this algorithm. Additionally, we describe changes that can be made to the algorithm presented to solve other related problems. Finally, we describe properties of T* on semi-collinear point sets.
- Subject
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
Copyright © 2017 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
- 2017
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
crosbie-optimalbichromaticplanespanningtreesforspecial.pdf | 2023-05-05 | Public | Download |