1975年,Shamos和Hoey利用计算机有效地计算了平面点集的Voronoi图,并发表了一篇著名的论文,计算几何从此诞生,成为计算机科学理论中一个新的富有生命力的领域.计算几何作为一门面向应用的学科,其研究成果已在计算机图形学、CAD&CAM、化学、统计分析、模式识别、地理数据库以及其他许多领域中得到了广泛的应用.并行计算是在并行计算机或分布式计算机等高性能计算系统上所作的超级计算,在生物计算,核能科学等很多领域里有着广泛的应用.可重构造网孔(RMESH)是一种新的的并行计算模型,它具有动态总线重构和处理单元间快速通讯的优点.随着RMESH的提出,相继出现了常数时间的排序和并行前缀和等著名的算法,这为在这种模型上的其他算法研究提供了有力的支持.从九十年中期开始,逐渐在RMESH上出现了二维凸壳、二维Voronoi图和最近邻等问题的并行算法,并且这些算法的时间复杂度都相当的好.因此,RMESH上的并行几何算法引起了普遍的关注.该文主要围绕下述几个计算儿何问题进行研究,并在RMESH上设计相关问题的并行算法:(1)可重构网孔机器上n个平面点的k-近邻算法.对于n个点的平面点集S,我们在规模为n×n的可重构造网孔机器上首次提出了时间复杂度为O(k)的k-近邻并行算法.与k次调用一个已知的常数时间最近邻RMESH并行算法相比,该算法降低了空间复杂度并减少了总线开关的重构次数.(2)三角剖分含有多边形空洞的多边形区域的常数时间算法.该文在n×n<1+ε>可重构造网孔机器上提出了一个三角剖分包含任意个多边形空洞的n顶点多边形的常数时间算法.首次实现了在常数时间内将空洞多边形区域划分成特殊单调多边形,然后在此基础上,提出了一个常数时间三角剖分所有特殊单调多边形的并行算法.据我们所知,这是第一个三角剖分含有任意个多边形空洞的多边形区域的常数时间算法.