Analysis of the n-dimensional quadtree decomposition for arbitrary hyper-rectangles
| dc.contributor.author | Faloutsos, Christos | en_US |
| dc.contributor.author | Jagadish, H.V. | en_US |
| dc.contributor.author | Manolopoulos, Yannis | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T09:57:22Z | |
| dc.date.available | 2007-05-23T09:57:22Z | |
| dc.date.issued | 1994 | en_US |
| dc.description.abstract | We 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.extent | 843646 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/5555 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 1994-86 | en_US |
| dc.subject | image processing | en_US |
| dc.subject | algorithms | en_US |
| dc.subject | computational geometry | en_US |
| dc.subject | computer vision | en_US |
| dc.subject | telemedicine | en_US |
| dc.subject | Systems Integration Methodology | en_US |
| dc.title | Analysis of the n-dimensional quadtree decomposition for arbitrary hyper-rectangles | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1