线对象邻接关系快速重构算法

摘要：

给定向量化坐标,计算n个线对象两两邻接关系,普通算法时间复杂度为O(n*n);理论最好时间复杂度为O(C),其中C是邻接关系的基数.基于散列桶,给出了建立线对象邻接关系的快速算法,其平均时间复杂度为O(n(1+1/r)),r为算法分配的桶数量与n的比,空间复杂度为O(n).证明了若不允许使用额外空间,则不可能使用排序算法解决该问题;给出了允许使用额外空间条件下的两遍排序算法,时间复杂度为O(n(lb n+1+2/r)).应用表明快速算法比普通算法速度提高1～3个数量级.

关键词：线对象、邻接关系、桶排序、算法分析

所属期刊栏目：28

分类号：TP311(计算技术、计算机技术)

在线出版日期：2008-03-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：245-247