A constrained minimum spanning tree problem
In this paper, we give an O(n(2)) algorithm for finding a point on a given line I which, if added to a given set of n points located on one side of l, will result in the minimum spanning tree.
spanning tree algorithm divide-and-conquer