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