The 1-line-fixed Minimum Bottleneck Steiner Tree Problem

In this thesis,we propose the 1-line-fixed minimum bottleneck Steiner tree problem,which is described as follows.Given a fixed line l on the Euclidean plane R2,a set P of n points r1,…,rn outside of the line l,it is asked to find one point s on the given line l to construct a spanning tree T of the set P?{s?,the objective is to minimize the length of the longest edge in the spanning tree of T,i.e.,minT max{w(e)|e ?T,T is a spanning tree mentioned-above},where w(e)is defined as the Euclidean distance between those two endpoints of this edge e of T.For the 1-line-fixed minimum bottleneck Steiner tree problem,we consider the cases where the points in the set P are all located at the same side and both sides of the line l.When the points in P are located at both sides of the line l,based on the results of solving the points in P are all located at the same side of the line I and the properties of optimal solutions,we present a polynomial time optimal algorithm in time O(n3 logn)to solve the problem.