可重构造网孔机器上简单多边形三角剖分的常数时间算法

简单多边形的三角剖分是计算几何的基本问题之一 ,在计算机图形学、地理信息系统及有限元方法等领域有许多重要的应用 .可重构造网孔机器是近几年出现的一种新的并行计算模型 ,由于其特有的灵活性 ,已经有很多领域的基本问题在这种模型上得到了研究 .该文在这种结构上考虑了简单多边形的三角剖分问题 :提出了一个将简单多边形分解为特殊单调多边形的算法 ,并在规模为 n× n的可重构造网孔机器上实现了常数时间分解单调多边形为特殊单调多边形的并行算法 ,基于这个算法得到了一个 n× n的机器上常数时间三角剖分单调多边形的算法 ;将这些算法稍加推广 ,并使用稍多的处理器 ,得到了一个在规模为 n× n1 +ε(0 <ε<1为常数 )的可重构造网孔机器上三角剖分简单多边形的常数时间算法 .就目前了解到的情况而言 。

可重构造网孔机器上k-近邻并行算法

最近邻问题是计算几何学中的基本问题之一 ,k 近邻是最近邻的扩展 ,它在VLSI设计、数据库检索、模式匹配以及图像处理等领域有着广泛的应用背景 对于点数为N的平面点集S ,在规模为N×N的可重构造网孔机器上 ,提出了时间复杂度为O(k)的求S中所有点k 近邻的并行算法