Analysis of the n-dimensional quadtree decomposition for arbitrary hyper-rectangles

dc.contributor.authorFaloutsos, Christosen_US
dc.contributor.authorJagadish, H.V.en_US
dc.contributor.authorManolopoulos, Yannisen_US
dc.description.abstractWe give a closed-form expression for the average number of n- dimensional quadtree nodes (ieces' or locks') required by an n-dimensional hyper-rectangle aligned with the axes. Our formula includes as special cases the formulae of previous efforts for 2- dimensional spaces [8]. It also agrees with theoretical and empirical results that the number of blocks depends on the hyper- surface of the hyper-rectangle and not on its hyper-volume. The practical use of the derived formula is that it allows the estimation of the space requirements of the n-dimensional quadtree decomposition. Quadtrees are used extensively in 2- dimensional spaces (geographic information systems and spatial databases in general), as well in higher dimensionality spaces (as oct-trees for 3-dimensional spaces, e.g. in graphics, robotics and 3-dimensional medical images [2]). Our formula permits the estimation of the space requirements for data hyper- rectangles when stored in an index structure like a (n- dimensional) quadtree, as well as the estimation of the search time for query hyper-rectangles. A theoretical contribution of the paper is the observation that the number of blocks is a piece-wise linear function of the sides of the hyper-rectangle.en_US
dc.format.extent843646 bytes
dc.relation.ispartofseriesISR; TR 1994-86en_US
dc.subjectimage processingen_US
dc.subjectcomputational geometryen_US
dc.subjectcomputer visionen_US
dc.subjectSystems Integration Methodologyen_US
dc.titleAnalysis of the n-dimensional quadtree decomposition for arbitrary hyper-rectanglesen_US
dc.typeTechnical Reporten_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
823.87 KB
Adobe Portable Document Format