The 1-line-fixed Euclidean 2-Steiner Tree Problem

In this thesis,we propose the 1-line-fixed Euclidean k-Steiner tree problem,which is specifically defined as follows.Given a fixed line l on the Euclidean plane,a set P of n points p1,...,pn outside of the line l and a positive integer k,it is asked to find k'points x1,...,xk'(1?k'?k)on the line l to construct a spanning tree T of the set P?{x1,...,xk'} such that any edge of T does not internally cross the line l,the objective is to minimize the weight of T,i.e.,min{?e?T w(e)| T is a spanning tree mentioned-above},where w(e)=0 if two endpoints of each edge e of T are on the line l,otherwise w(e)is defined as the Euclidean distance between those two endpoints of this edge e of T.We consider the problem for the case k=2,i.e.,the 1-line-fixed Euclidean 2-Steiner tree problem.When the points in P are all located at the same side of the line l,we design an exact algorithm in time O(n2)to solve the problem.When the points in P are located at both sides of the line l,using the results that we obtain to solve the previous version and some properties of optimal solutions,we present an exact algorithm in time O(n2) to solve the problem.