任意两多边形相交点最大可能数目的计算法

ALGORITHM FOR COMPUTING THE MAXIMUM NUMBER OF INTERSECTIONS OF TWO POLYGONS

本文提出计算任意两多边形相交点最大可能数目的算法．文中导出并通过实例证明，如果已知两多边形Ｐ和Ｑ分别有ｐ和ｑ个顶点，那末就能够确定它们之间最大可能的交点数目，这样使我们能有效地分析某些领域求解问题算法的复杂性以及解其它有关问题．

This paper proposes an algorithm for computing the maximum number of intersections of two polygons. It is demonstrated that the maximum numbers of intersections of two polygons P and Q which have p and q venices respectively can be computed. Thus the complexity of algorithms solving the problem and other related problems in some fields can be analyzed effectively.