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

被引：3

作者：

周培德

张金玲

机构：

[1] 北京理工大学计算机系

[2] 北京华虹NEC集成电路设计有限公司北京

[3] 北京

来源：

工程图学学报 | 2003年 / 04期

关键词：

计算机应用; 线段集凸壳; 平面扫描方法; 算法;

D O I：

暂无

中图分类号：

TP391.41 [];

学科分类号：

080203 ;

摘要：

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

引用

页码：110 / 115

页数：6