Parallel Algorithms for Geometric Problems

摘要

The existence of parallel computing systems and the important applications of geometric solutions have motivated our study on the design and analysis algorithms for solving geometric problems on two parallel computing systems: the Shared Memory Machine (SMM) and the Cube-Connected-Cycles (CCC). The validity of the first SMM resides in uncovering the inherent data-dependence of the problems, while that of the CCC, which complies with the VLSI technological constraints, is the development of practical parallel algorithms. It is shown that solutions to geometric problems can be organized to reveal a large amount of parallelism, which can be exploited to substantially reduce the computation time.