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

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