Vertex Quadtree and Octree for Geometric Modeling : Their Average Storage and Time Complexities

We developed new quadtree and octree representation schemes which reduce the storage requirements from exponential to polynomial. The new schemes not only lessen the large storage requirements of the existing quadtree and octree representation schemes but guarantee an exact representation of the original object. These are made possible by adopting a new set of termination conditions that ensure finiteness of the quadtree and octree during the decomposition. These new data structures are analyzed theoretically and tested empirically. For space complexity, we analyzed its best case, worst case, and average case. Given an -gon, we show that the expected number of nodes in our quadtree isO() For a polyhedron with faces, the expected number of nodes in the new octree is O(). For time complexity, we again analyzed the best, worst, and average cases for constructing such quadtree and octree and find the average to be the same as those of the space complexity. Finally, random - gons are generated as test data. Regression equations are fitted and are shown to support the claims on the average case performance.