文件名称：凸多边形最小面积四边形包围盒算法 (2006年)
文件大小：1.76MB
文件格式：PDF
更新时间：2024-05-26 13:57:37
自然科学 论文
针对凸多边形的最小面积四边形包围盒问题进行研究，通过数学推导证明，得出了凸多边形的最小面积四边形包围盒的四边都是多共点边，或三边是多共点边而另一边（单共点边）中点与凸多边形的一顶点重合等一系列结论。依据此结论设计了时间复杂度为O（n4）的算法，依据本算法可以构造出凸多边形面积最小的凸四边形包围盒，而且其算法的复杂度仅与凸多边形的边数n相关，是多项式级的复杂度。运算实例表明了算法的正确性和有效性。