论文部分内容阅读
简单多边形的三角剖分是计算几何的基本问题之一 ,在计算机图形学、地理信息系统及有限元方法等领域有许多重要的应用 .可重构造网孔机器是近几年出现的一种新的并行计算模型 ,由于其特有的灵活性 ,已经有很多领域的基本问题在这种模型上得到了研究 .该文在这种结构上考虑了简单多边形的三角剖分问题 :提出了一个将简单多边形分解为特殊单调多边形的算法 ,并在规模为 n× n的可重构造网孔机器上实现了常数时间分解单调多边形为特殊单调多边形的并行算法 ,基于这个算法得到了一个 n× n的机器上常数时间三角剖分单调多边