论文部分内容阅读
首先证明寻求平面上线段集凸壳问题的下界是O(nlogn),其方法是将平面上线段集凸壳问题与排序问题联系起来,由排序问题的下界推得平面上线段集凸壳问题的下界。然后提出一个算法,计算平面上线段集凸壳问题,其基本思想是将不交线段集中的线段按其端点的x,y坐标排序,并重排线段序。然后用平面扫描方法分段完成凸壳的构造。该算法的时间复杂性是O(nlogn)。