计算平面点集凸包的实时插入算法

• 作者: 刘萍
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: 凸包 实时插入算法 Graham扫描算法
• 年，卷（期）: 2013,（1）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 12-14
• 页数: 3页
• 分类号: TP301.6
• 字数: 3106字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2013.01.004

摘要

讨论平面点集的凸包实时插入算法.算法基于Graham扫描算法,对3个点检测顺序的转向.本文证明,当S的N个点以流的形式进入系统,计算S的凸包所需的检测次数小于3N.