CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

PDF papers
authors Finkel, R. A. and Bentley, Jon L.
year 1974
title Quad Trees : A Data Structure for Retrieval on Composite Keys
source Acta Informatica. 1974. vol. 4: pp. 1-9 : ill. includes bibliography
summary The quad tree is a data structure appropriate for storing information to be retrieved on composite keys. The paper discusses the specific case of two-dimensional retrieval, although the structure is easily generalized to arbitrary dimensions. Algorithms are given both for straightforward insertion and for a type of balanced insertion into quad trees. Empirical analyses show that the average time for insertion is logarithmic with the tree size. An algorithm for retrieval within regions is presented along with data from empirical studies which imply that searching is reasonably efficient. The paper defines an optimized tree and presents an algorithm to accomplish optimization in n log n time. Searching is guaranteed to be fast in optimized trees. Remaining problems include those of deletion from quad trees and merging of quad trees, which seem to be inherently difficult operations
keywords quadtree, data structures, algorithms, search, sorting
series CADline
references Content-type: text/plain
last changed 2003/06/02 11:58
pick and add to favorite papersHOMELOGIN (you are user _anon_332395 from group guest) CUMINCAD Papers Powered by SciX Open Publishing Services 1.002