【摘要】 设Ｐ和Ｑ是平面内任意两个互不相交的凸多边形，目前确定Ｐ与Ｑ的可碰撞区域的最佳串行算法时间复杂度为Ｏ（ｎ＋ｍ），其中ｎ和ｍ分别为凸多边形Ｐ和Ｑ的顶点个数．在该算法的基础上构造了一个易于并行化的求支撑点的串行算法，进而给出了在ＭＩＭＤ－ＣＲＥＷ模型上确定可碰撞区域的并行算法，其时间复杂度为Ｏ（（Ｓ＋ｌｏｇ＿２（ｎ＋ｍ））ｌｏｇ＿２（ｎ＋ｍ）／ｌｏｇ＿２Ｓ），其中Ｓ为处理机个数更多还原

【Abstract】 Let P and Q be two arbitrary disjoint convex polygons in a plane. the time-complexityof the optimal serial algorithm currently used for determining the region of collision possibili-ty between P and Q is O（n+m）,where n and m refer to the number of vertices in convexpolygons P and Q, respectively. Based on this serial algorithm,a serial algorithm easy toparallelize for finding the supporting point according to the properties of the inclined support-ing line of the convex polygon is developed.The algorithm is then parallelized on the modelMIMD-CREW using the divide-and-rule strategy so as to work out a parallel algorithm todetermine the region of possible collision of convex polygons.the time-complexity of the al-gorithm proposed is O（（S+log₂（n+m））log₂（n+m）/log₂S）,where S is the number of the processors.更多还原