A strip-splitting-based optimal algorithm for decomposing a query window into maximal quadtree blocks |
| |
| Authors: | Yao-Hong Tsai Kuo-Liang Chung Wan-Yu Chen |
| |
| Affiliation: | Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ. of Sci. & Technol., Taipei, Taiwan; |
| |
| Abstract: | Decomposing a query window into maximal quadtree blocks is a fundamental problem in quadtree-based spatial database. Recently, Proietti presented the first optimal algorithm for solving this problem. Given a query window of size n/sub 1//spl times/n/sub 2/, Proietti's algorithm takes O(n/sub 1/) time, where n/sub 1/=max(n/sub 1/, n/sub 2/). Based on a strip-splitting approach, we present a new optimal algorithm for solving the same problem. Experimental results reveal that our proposed algorithm is quite competitive with Proietti's algorithm. |
| |
| Keywords: | |
|
|
