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

Quick algorithm for reconstructing line object adjacency relations

作　　者：廖名学[1] 范植华[1] 何晓新[1] 

机构地区：[1]中国科学院软件研究所,北京100080

出　　处：《计算机应用》2008年第1期245-247,共3页journal of Computer Applications

摘　　要：给定向量化坐标，计算n个线对象两两邻接关系，普通算法时间复杂度为O（n＊n）；理论最好时间复杂度为O（C），其中C是邻接关系的基数。基于散列桶，给出了建立线对象邻接关系的快速算法，其平均时间复杂度为O（n（1＋1／r）），r为算法分配的桶数量与n的比，空间复杂度为O（n）。证明了若不允许使用额外空间，则不可能使用排序算法解决该问题；给出了允许使用额外空间条件下的两遍排序算法，时间复杂度为O（n（1bn＋1＋2／r））。应用表明快速算法比普通算法速度提高1—3个数量级。Based on known coordinates of lines, the time complexity of usual algorithm for reconstructing adjacency relation among n line objects usually is O（n ＊ n） ; in theory, its optimal value is at least O（C） and C is the cardinal number of adjacency relation. Based on hashed-bucket sorting, a quick algorithm with O（ n（ 1 ＋ 1/r） ） average time complexity and with O（n） space complexity was given to reconstruct adjacency relation where r was the ratio of number of buckets used in the algorithm to n. It was proved that the problem can not be solved by sorting algorithm without extra space. With necessary extra space, a two-pass sorting algorithm with O[ n（ 1b n ＋ 1 ＋ 2/r） ] time complexity, was also given. Applications show that the performance of the quick algorithm is over about 1 - 3 orders of magnitude higher than that of the usual algorithm.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]