A sweeping line algorithm based on two dimensional region search

The authors present a new plane-sweep algorithm which is based on several primitive functions of region query for a number of overlapped rectangles in 2-D space. A theorem proves that the presented algorithm can be built from any spatial data structure with region query functions. Experimental results presented show that this algorithm has been successfully implemented in C language based on two kinds of spatial data structures, the multiple storage quad tree and the quad list quad tree. This algorithm can be performed in a time complexity of O(N log N)