计算几何与并行算法

本文首先介绍了计算几何的基本概念,论述了计算几何的四个基本问题,即几何搜索问题、相交问题、邻接问题及凸壳问题。然后重点分析了凸壳构造问题,介绍了其最佳串行算法、及相应的并行算法。接着对一些计算几何的串行及并行算法进行了分析比较。最后提出了笔者对新一代并行计算机系统上设计计算几何并行算法的看法。

Computational Geometry and Parallel Algorithms

This paper first introduces the basic concepts of computational geometry and four basic problems,i.e. geometry searching.intersection, proximity and computing convex hull problems,and their applications. Second,the best known sequential algorithm for convex hulls is described and its parallelized version is summarized. Third, some computational geometry algo rithms are compared and analysed. Finally,some of the author's viewpoints on computational geometry on modern parallel computers are presented.