# An effective way to represent quadtrees

@article{Gargantini1982AnEW, title={An effective way to represent quadtrees}, author={Irene Gargantini}, journal={Commun. ACM}, year={1982}, volume={25}, pages={905-910} }

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, (<italic>i</italic>) encoding a pixel from a 2<supscrpt><italic>n</italic></supscrpt> × 2… Expand

#### Paper Mentions

#### 737 Citations

Translation, Rotation and Superposition of Linear Quadtrees

- Mathematics, Computer Science
- Int. J. Man Mach. Stud.
- 1983

Procedures for translating and rotating a region are presented and the superposition of binary images with different characteristics is considered, showing translation, rotation, and superposition to be O(N log N) operations. Expand

Multi-colored quadtrees for GIS: Exploiting bit-parallelism for rapid boolean overlay

- Mathematics, Computer Science
- Pattern Recognit. Lett.
- 1988

This paper presents an alternative database scheme where a layer is stored as a single multicolored quadtree, using a bit-list to store values at higher nodes in the tree, using parallel bit-masking operations. Expand

Data structures for quadtree approximation and compression

- Mathematics, Computer Science
- CACM
- 1985

A number of data structures for representing images by quadtrees without pointers are discussed and Sequences of approximations using various combinations of locational codes of GB and GW nodes are proposed and shown to be superior to approximation methods based on truncation of nodes below a certain level in the tree. Expand

Comment on Quad- and Octtrees

- Computer Science
- CACM
- 1984

It is claimed that studying the case of binary division provides for a more general understanding of the underlying structures and that less attention is needed on the separate results concerning quadand octtrees. Expand

Data Structures for Quadtree

- Mathematics
- 1985

A number of data structures for representing images by quadtrees without pointers are discussed. The image is treated as a collection of leaf nodes. Each leaf node is represented by use of a… Expand

Algorithm to expand regions represented by linear quadtrees

- Computer Science
- Image Vis. Comput.
- 1988

An algorithm is presented that changes to ‘black’ those ‘white’ pixels within a specified distance of any ‘ black’ pixel in an image represented by a linear quadtree, useful for answering queries in a geographic information system. Expand

Compressed quadtree with content-addressable memory

- Computer Science
- Proceedings of 1st International Conference on Image Processing
- 1994

The author proposes a new hierarchical data structure, named as quad-quadtree, which is based on the recursive subdivision of an image into 16 equal-sized sub-images until each is homogeneous or until a sufficiently fine resolution is reached. Expand

Quadtrees and Morton Indexing

- Computer Science
- Encyclopedia of Algorithms
- 2016

The quadtree describes a class of data structures for geometric objects. A quadtree partitions space hierarchically using a stopping rule that decides when a region is small enough so that it does… Expand

FAST REGION EXPANSION FOR QUADTREES•

- 2007

A one-pa.ss algorithm is presented to perform region expansion in images that are represented by quadtrees. The algorithm changes to BLACK those WHITE pixels within a specified distance of any BLACK… Expand

Parallel Processing of Linear Quadtrees on a Mesh-Connected Computer

- Computer Science
- J. Parallel Distributed Comput.
- 1989

This paper uses a scheme which represents a quadtree by its leaf nodes; each node is represented by the coordinates of the upper left corner of its corresponding block and its color and size. Expand

#### References

SHOWING 1-10 OF 15 REFERENCES

Operations on Images Using Quad Trees

- Computer Science, Medicine
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- 1979

Warnock-type algorithms are presented for building the quad tree for the picture of the boundary of apolygon, and for coloring the interior of such a polygon. Expand

An Algorithm for Converting Rasters to Quadtrees

- Computer Science, Medicine
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- 1981

An algorithm is presented for constructing a quadtree for a binary image given its row-by-row description. The algorithm processes the image one row at a time and merges identically colored sons as… Expand

Connected Component Labeling Using Quadtrees

- Computer Science
- JACM
- 1981

Analysis of the algorithm reveals that its worst case average execution time is bounded by a quantity proportional to the product of the log of the region's diameter and the number of blocks comprising the area connected by the components. Expand

On a Method of Binary-Picture Representation and Its Application to Data Compression

- Computer Science, Medicine
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- 1980

It was made clear that the DF-expression is a very effective technique as a data compression for binary pictorial patterns not only because it yields high data compression but also because its coding and decoding algorithms are very feasible. Expand

Region representation: boundary codes from quadtrees

- Computer Science
- CACM
- 1980

This paper presents an algorithm for converting from quadtrees to a simple class of boundary codes and is shown to have an execution time proportional to the perimeter of the region. Expand

Organization and Access of Image Data by Areas

- Computer Science, Medicine
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- 1979

Algorithms enabling efficient retrieval of subpicture areas from sequential and direct access files are presented, and examples show that improved retrieval response is possible from using NUMERIC to sort lists of areas to be recalled. Expand

Representation of Three-Dimensional Digital Images

- Computer Science
- CSUR
- 1981

This paper attempts to unify data structures for representing interior, surface, and structural information of objects in such images by companng their relative efficium by survey of three-dimensmnal spatial-data representation methods emphasizing techniques that apply to cellular images. Expand

Region representation: quadtrees from boundary codes

- Computer Science
- CACM
- 1980

An algorithm is presented for constructing a quadtree for a region given its boundary in the form of a chain code. Analysis of the algorithm reveals that its execution time is proportional to the… Expand

Oct-trees and their use in representing three-dimensional objects

- Mathematics
- 1980

Abstract Many of the programming techniques used in solving two-dimensional problems can be extended to three dimensions. Here oct-trees are developed as a three-dimensional analog of quad-trees.… Expand

Translation of Decision Tables

- Computer Science
- ACM Comput. Surv.
- 1974

Decomposition and conversion algorithms for translating decision tables are surveyed and contrasted under two broad categories: the mask rule technique and the network technique. Also, decision table… Expand