A sweeping line algorithm based on two dimensional region search

Author

Hsiao, Pei-Yung ; Li, John Kun-Han ; Tsai, Chia-Chun

Author_Institution

Dept. of Comput. & Inf. Sci., Nat. Chiao Tung Univ., Hsin Chu, Taiwan

fYear

1990

fDate

24-27 Sep 1990

Firstpage

496

Abstract

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)

Keywords

computational complexity; search problems; C language; multiple storage quad tree; overlapped rectangles; plane-sweep algorithm; primitive functions; quad list quad tree; region query functions; spatial data structure; sweeping line algorithm; time complexity; two dimensional region search; Algorithm design and analysis; Application software; Computational geometry; Computer science; Data structures; Image processing; Information science; Pattern recognition; Routing; Tree data structures;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer and Communication Systems, 1990. IEEE TENCON'90., 1990 IEEE Region 10 Conference on

Print_ISBN

0-87942-556-3

Type

conf

DOI

10.1109/TENCON.1990.152659

Filename

152659