Abstract: A new.quadtree construction algorithm is presented in this paper. The algorithm reduces the inserted nodes and auxiliary storage space, compared with the optimal quadtree construction algorithm in the literature 3. A new image data structure called digital search tree, as a mid storage structure of linear quadtrees is also presented. The time and space efficiency of the new algorithm is higher than the old one presented in the literature3.