quadtree complexity theorem

(definition)

Definition: The number of nodes in a quadtree region representation for a simple polygon (i.e. with nonintersecting edges and without holes) is O(p+q) for a 2^q× 2^q image with perimeter p measured in pixel widths. In most cases, q is negligible, and thus, the number of nodes is proportional to the perimeter. It also holds for three-dimensional data where the perimeter is replaced by surface area, and in general for d-dimensions where instead of perimeter we have the size of the (d-1)-dimensional interfaces between the d-dimensional objects.

Note: From Algorithms and Theory of Computation Handbook, page 18-24, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 17 December 2004.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "quadtree complexity theorem", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/quadtreecplx.html