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

笔者针对平面上不相交线段序列的遍历问题进行研究,分析Rubber-band算法在解决该问题时的局限性,提出采用凸链分解与分段组合优化相结合的技术,设计一个时间复杂度为O(nlog^2n)的快速求解算法——BST算法,并采用事后分析方法,对BST算法与Rubber-band算法进行了对比。结果表明,BST算法的性能优于Rubber-band算法,是到目前为止求解该问题的最优算法。