A strip-splitting-based optimal algorithm for decomposing a query window into maximal quadtree blocks

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(1) x n(2), Proietti's algorithm takes O(n(j)) time, where n(l) = max(n(1), n(2)). based on a strip-splitting approach, this paper presents a new optimal algorithm for solving the same problem. Experimental results reveal that our proposed algorithm is quite competitive with Proietti's algorithm.