寻求平面上线段集凸壳的扫描算法

摘要：

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

关键词：计算机应用、线段集凸壳、平面扫描方法、算法

所属期刊栏目：24

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2004-02-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：110-115