凸多边形最小面积四边形包围盒算法

• 作者: 彭雷 戴光明 王茂才
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 工学
• 关键词: 凸多边形 最小四边形包围盒 多共点边
• 年，卷（期）: 2006,（6）
• 页码范围: 71-73
• 页数: 3页
• 分类号: TP391.73
• 字数: 1818字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-4512.2006.06.022

摘要

针对凸多边形的最小面积四边形包围盒问题进行研究,通过数学推导证明,得出了凸多边形的最小面积四边形包围盒的四边都是多共点边,或三边是多共点边而另一边(单共点边)中点与凸多边形的一顶点重合等一系列结论.依据此结论设计了时间复杂度为O(n4)的算法,依据本算法可以构造出凸多边形面积最小的哪凸四边形包围盒,而且其算法的复杂度仅与凸多边形的边数n相关,是多项式级的复杂度.运算实例表明了算法的正确性和有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	戴光明	中国地质大学计算机学院	77	488	11.0	17.0
2	王茂才	中国地质大学计算机学院	22	102	7.0	9.0
3	彭雷	中国地质大学计算机学院	20	120	8.0	10.0