Optimal Bichromatic Plane Spanning Trees For Special Point Sets
Kimberly Crosbie · 2017
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.16 Illustration of Base Case 5 . . . . . . . . . . . . .