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

• 作者: 周培德
• 来源期刊: 工程图学学报
• 学科: 工学
• 关键词: 计算机应用 线段集凸壳 线段链方法 算法
• 年，卷（期）: 2003,（2）
• 所属期刊栏目: 计算几何
• 页码范围: 116-119
• 页数: 4页
• 分类号: TP301.6
• 字数: 2646字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-0158.2003.02.018

摘要

首先证明寻求平面上线段集凸壳问题的下界是O(n log n),其方法是将平面上线段集凸壳问题与排序问题联系起来,由排序问题的下界推得平面上线段集凸壳问题的下界.然后提出一个算法,计算平面上线段集凸壳问题,其基本思想是将线段集中的线段转换成平面上的简单多边形链,接着计算该简单多边形链的凸壳即得到所要求的凸壳.该算法的时间复杂性是O(n log n).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周培德	北京理工大学计算机系	28	414	12.0	20.0