Quick algorithm for reconstructing line object adjacency relations
Xiaoxin He · Journal of Computer Applications · 2008
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 On(lb 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.