| 凸多边形最小面积四边形包围盒算法 |
| |
| 引用本文： | 戴光明,王茂才,彭雷.凸多边形最小面积四边形包围盒算法[J].华中科技大学学报(自然科学版),2006,34(6):71-73. |
| |
| 作者姓名： | 戴光明 王茂才 彭雷 |
| |
| 作者单位： | 中国地质大学,计算机学院,湖北,武汉,430074 |
| |
| 摘 要： | 针对凸多边形的最小面积四边形包围盒问题进行研究,通过数学推导证明,得出了凸多边形的最小面积四边形包围盒的四边都是多共点边,或三边是多共点边而另一边(单共点边)中点与凸多边形的一顶点重合等一系列结论.依据此结论设计了时间复杂度为O(n4)的算法,依据本算法可以构造出凸多边形面积最小的凸四边形包围盒,而且其算法的复杂度仅与凸多边形的边数n相关,是多项式级的复杂度.运算实例表明了算法的正确性和有效性.
|
| 关 键 词： | 凸多边形 最小四边形包围盒 多共点边 |
| 文章编号： | 1671-4512(2006)03-0071-03 |
| 收稿时间： | 03 23 2005 12:00AM |
| 修稿时间： | 2005年3月23日 |
Algorithm for smallest quadrangle encasing box of convex polygon |
| |
| Dai Guangming,Wang Maocai,Pen Lei.Algorithm for smallest quadrangle encasing box of convex polygon[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,2006,34(6):71-73. |
| |
| Authors: | Dai Guangming Wang Maocai Pen Lei |
| |
| Institution: | School of Computer, China University of Geosciences, Wuhan 430074, China. |
| |
| Abstract: | |
| |
| Keywords: | convex polygon smallest quadrangle encasing box side |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
