(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 2q× 2q 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 E. Black.
Entry modified Fri Dec 17 12:06:55 2004.
HTML page formatted Wed Oct 26 09:48:01 2005.
Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "quadtree complexity theorem", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/quadtreecplx.html
