一种求凸多边形宽度的优化算法

• 作者: 李俨 焦裕松 王新民 陈海
• 来源期刊: 工程图学学报
• 学科: 工学
• 关键词: 计算几何 优化算法 点边式 凸多边形
• 年，卷（期）: 2011,（2）
• 所属期刊栏目: 几何与图形学
• 页码范围: 5-9
• 分类号: TP301.6
• 字数: 3769字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-0158.2011.02.002

摘要

提出了一种优化的线性时间算法计算凸多边形的宽度.首先证明了凸多边形的宽度只可能介于"点边式"跨度之间,缩小了宽度的计算范围.其次提出了一种距离比较算法,降低了凸多边形跨度的计算量.最后,在"点边式"基本算法和距离比较算法的基础上,提出了计算宽度的优化算法.仿真分析表明,提出的优化算法提高了计算凸多边形宽度的效率,算法的时间复杂性降为O(n).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王新民	西北工业大学自动化学院	188	1307	18.0	24.0
2	李俨	西北工业大学自动化学院	53	386	11.0	17.0
3	陈海	西北工业大学自动化学院	6	84	5.0	6.0
4	焦裕松	西北工业大学自动化学院	3	60	3.0	3.0