遍历平面上给定线段序列的快速方法  

A Fast Algorithm for Visiting Segment Sequences Given in the Plane

作　　者：王立娟[1] 刘瑞杰[1] 王璨[1] Wang Lijuan;Liu Ruijie;Wang Can(School of Information Science,Dalian University of Science and Technology,Dalian Liaoning 116052,China)

机构地区：[1]大连科技学院信息科学学院,辽宁大连116052

出　　处：《信息与电脑》2018年第5期54-56,共3页Information & Computer

基　　金：辽宁省科学研究一般项目"平面内有序几何物体的最优遍历方法及其应用研究"(NO.L2015105);辽宁省自然科学基金项目"离散几何物体序列的快速遍历算法及其应用研究"(NO.20170540147)

摘　　要：笔者针对平面上不相交线段序列的遍历问题进行研究,分析Rubber-band算法在解决该问题时的局限性,提出采用凸链分解与分段组合优化相结合的技术,设计一个时间复杂度为O(nlog^2n)的快速求解算法——BST算法,并采用事后分析方法,对BST算法与Rubber-band算法进行了对比。结果表明,BST算法的性能优于Rubber-band算法,是到目前为止求解该问题的最优算法。The problem of visiting disjoint segments in given order will be studied in this paper.First,by analyzing the limitations of the Rubber-band algorithm,we present the division of convex chain and combination optimization technology,and design a fast algorithm with the O(nlog2 n)time,denoted by BST,where n is the total number of all segments.Furthermore,we test the two algorithms to compare the runtime efficiency.The results show that the BST algorithm is superior to Rubber-band algorithm,and it is the optimal algorithm to visit the disjoint segments sequence so far.

关 键 词：凸链分解 二分检索树 分段组合优化 Rubber-band算法 

分 类 号：O18[理学—数学]