判定凸多边形可碰撞性的并行算法

A Parallel Algorithm for Determining Possible Collision between Convex Polygons

设Ｐ与Ｑ是平面内任意两个互不相交的凸多边形，为任一给定方向，研究并行判定Ｐ沿以平移方式移动可与Ｑ碰撞的问题。采用Ｓ分搜索策略，在ＭＩＭＤ－ＣＬ模型上给出了求解此问题的并行算法，并证明了算法的正确性．最坏情况下，在超立方结构上算法的时间复杂度为Ｏ（ｌｏｇ＿２（ｍ＋ｎ）），通讯复杂度为Ｏ（ｅｌｏｇ＿２（ｍ＋ｎ）／ｌｏｇ＿２Ｓ）

Let p=(p0,p1,…,p(n-1))and Q=(q0 ,q1,…,q(m-1))be two arbitrary disjoint convexpolygons and an arbitrary direction in plane. The determination of whether P will collidewith Q when P moves parallelly in the direction of is studied. A parallel algorithm usingthe parallel searching strategy is given. The determination problem is transformed into asearching one and then the S-way searching strategy is used on model MIMD-CL. After atmost [log_2(n+ m)/log_2S] iterations, the maximum and minimum points can be found. Inworst case,the time-complexity of this algorithm for a hypercube of e sides is O(log_2(m+n))and the communication-complexity is O(elog_2(m+n)log_2S),where S is the number ofthe processors.