已知拓扑下的4度Steiner树算法

Algorithm for 4Degree Steiner Tree Topology

设Ｎ为平面上２ｎ个固定点的集合，Ｍ为ｎ－２个可动点的集合，Ｅ为连接这些点的边的集合（也称作拓扑）．设Ｅ为点集Ｖ上的满４度Ｓｔｅｉｎｅｒ拓扑（满Ｓｔｅｉｎｅｒ拓扑也就是满足固定点的度为１，可动点的度为４的树的拓扑），Ｈ（Ｅ）为包含Ｅ在内的所有Ｅ的退化拓扑的集合．文中构造了计算拓扑属于Ｈ（Ｅ）的４度Ｓｔｅｉｎｅｒ树算法，并证明了算法的时间复杂性是Ｏ（ｎ２）．

Let N denote a set S of 2 n fixed points and M a set of m moving points in the plane. A set E of edges connecting these points is called a topology. Let E be a full 4 degree Steiner topology (i.e. the topology of the tree which contains fixed points of degree 1 and moving points of degree 4) on the set V such that the set of topology H(E) includes E and it′s degenerate cases. An algorithm is presented for finding a 4 degree Steiner tree whose topology belongs to H(E) . The time complexity of the algorithm is O(n 2) .