【摘要】 设欧氏平面上直线L的一侧有n个点的点集N,L上则有一个禁区集合F,现要在L上禁区集合以外找一点p,使得联结N∪{p}的最小网络之长达到最短。文章对这一问题提出了一个O(n2)的近似算法,其性能比为32。更多还原

【Abstract】 Let L be a straight line in an Euclidean plane, and N be a set of n points on the same side of L, F be a forbidden region in L consisting of some intervals. The problem is to find a point P in L outside F such that the length of the network interconnecting the set N∪｛p｝ is minimized. An O(n~2) approximation algorithm is presented, whose performance ratio is shown to be 32 .更多还原