在MIMD—CREW模型上确定凸多边形可碰撞区域的并行算法 |
| |
引用本文: | 崔国华,李庆华.在MIMD—CREW模型上确定凸多边形可碰撞区域的并行算法[J].华中理工大学学报,1994,22(6):5-9. |
| |
作者姓名: | 崔国华 李庆华 |
| |
摘 要: | 设P和Q是平面内任意两个互不相交的凸多边形,目前确定P与Q的可碰撞区域的最佳串行算法时间复杂度为O(n+m),其中n和m分别为凸多边形P和Q的顶点个数。在该算法的基础构造了一个易于并行化的求支撑点的串行算法,进而给出了在MIMD-CREW模型上确定可碰撞区域的并行算法,其时间复杂度为O((S+log2(n+m)log2(n+m)/log2S),其中S为处理机个数。
|
关 键 词: | 并行算法 凸多边形 可碰撞性 |
本文献已被 维普 等数据库收录! |
|