关键词: 计算几何, 优化算法, 点边式, 凸多边形

Abstract: An optimal linear time algorithm is proposed to calculate the width of convex polygons. It is proved that the width of a convex polygon only be found between the span of vertex-edge pairs. In this way, the range of calculation narrows down. Then an algorithm using distance comparison is investigated to reduce the calculation of the span. Based on the basic algorithm of vertex-edge pairs and the distance comparison, the optimal algorithm for calculating the width is proposed. The simulation results show that the proposed algorithm greatly improves the efficiency of caculating the width of convex polygons, and reduces the time complexity to O(n).

Key words: computational geometry, optimal algorithm, vertex-edge pairs, convex polygon