在MIMD－CREW模型上确定凸多边形可碰撞区域的并行算法

A Parallel Algorithm for Determining the Possible Collision Region of Convex Polygons on Model MiMD-CREW

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

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_2(n+m))log_2(n+m)/log_2S),where S is the number of the processors.