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