1982/12/01 by Irene Gargantini · 640 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Code (set theory) #Computer science #Digital Image Processing Techniques #Integer (computer science) #Logarithm #Mathematics #Medical Image Segmentation Techniques #Node (physics) #Quadtree #Superposition principle #Time complexity
paper · pdf · doi:10.1145/358728.358741
published in Communications of the ACM 25(12), 905-910 (Association for Computing Machinery)
openalex publication_date 1982/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
A quadtree may be represented without pointers by encoding each black node with a quaternary integer whose digits reflect successive quadrant subdivisions. We refer to the sorted array of black nodes as the “linear quadtree” and show that it introduces a saving of at least 66 percent of the computer storage required by regular quadtrees. Some algorithms using linear quadtrees are presented, namely, ( i ) encoding a pixel from a 2 n × 2 >n array (or screen) into its quaternary code; ( ii ) finding adjacent nodes; ( iii ) determining the color of a node; ( iv ) superposing two images. It is shown that algorithms ( i )-( iii ) can be executed in logarithmic time, while superposition can be carried out in linear time with respect to the total number of black nodes. The paper also shows that the dynamic capability of a quadtree can be effectively simulated.