Title :
A new plane-sweep algorithm based on spatial data structure for overlapped rectangles in 2-D plane
Author :
Hsiao, Pei-Yung ; Tsai, Chia-Chun
Author_Institution :
Nat. Chiao Tung Univ., Hsinchu, Taiwan
fDate :
31 Oct-2 Nov 1990
Abstract :
The authors present a novel plane-sweep algorithm based on spatial data structures with region query operations. Such an algorithm is applicable to the problems of VLSI layout design and image processing. It has a computing time of O(N log N) and allows the functional operations of region search of the spatial data structures to be useful in solving some of the specified problems. This algorithm has been successfully implemented in C language; it was based on two kinds of spatial data structures; multiple storage quad tree and quad list quad tree. This plane-sweep algorithm also has been successfully applied to problems of layout compaction, design rule checking, and minimum reliable partition
Keywords :
computational complexity; computational geometry; computer graphics; data structures; trees (mathematics); 2D plane; C language; VLSI layout design; computing time; design rule checking; image processing; layout compaction; minimum reliable partition; multiple storage quad tree; overlapped rectangles; plane-sweep algorithm; quad list quad tree; region query operations; region search; spatial data structure; Algorithm design and analysis; Data engineering; Data structures; Information science; Partitioning algorithms; Routing; Sorting; Space technology; Tree data structures; Very large scale integration;
Conference_Titel :
Computer Software and Applications Conference, 1990. COMPSAC 90. Proceedings., Fourteenth Annual International
Conference_Location :
Chicago, IL
Print_ISBN :
0-8186-2054-4
DOI :
10.1109/CMPSAC.1990.139379
