Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-03-15
2005-03-15
Robinson, Greta (Department: 2167)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06868420
ABSTRACT:
A method traverses a bi-tree stored in a memory to locate application specific data stored in the memory and associated with the bi-tree. The bi-tree comprises a spatial partitioning of an N-dimensional space into a hierarchy of cells. Starting from a root cell enclosing the N-dimensional space, each cell is successively and conditionally partitioned into 2Nchild cells along the cell's N mid-planes. Each cell of the bi-tree has associated characteristics comprising the application specific data and child cells are indexed directly from a parent cell. First, a set of locational codes, a cell of the bi-tree, and a termination condition are specified. Next, the characteristics of the cell are tested to see if they satisfy the termination condition. If the termination condition is not satisfied, an arithmetic operation on the set of locational codes is performed to directly index a next cell to be tested. Otherwise, the cell identifies a target cell. Finally, the application specific data of the target cell is retrieved from the memory.
REFERENCES:
patent: 5459831 (1995-10-01), Brewer et al.
patent: 5937190 (1999-08-01), Gregory et al.
patent: 6401038 (2002-06-01), Gia
George Cho, “A self Teaching Guide for GIS”, Feb. 12, 2001,http://64.233.161.104/search?q=cache:N7Sm3oUthUkJ:www.rz.uni-hohenheim.de/anw/programme/gis/GIS_Manual_self_learning.pdf+%22locational+code%22+copyright+2001&hl=en.*
Pritchard, “Direct Access Quadtree Lookup,” Game Programming Gems 2, ed. DeLoura, Charles River Media, Hingham, MA, 2001.
Stolte and Caubet, in “Discrete Ray-Tracing of Huge Voxel Spaces,” Computer Graphics Forum, 14(3), pp. 383-394, 1995.
Bhattacharya in “Efficient Neighbor Finding Algorithms in Quadtree and Octree,” M.T. Thesis, Dept. Comp. Science and Eng., India Inst. Technology, Kanpur, 2001.
Havran, “A Summary of Octree Ray Traversal Algorithms,” Ray Tracing News, 12(2), pp. 11-23, 1999.
Frisken Sarah F.
Perry Ronald N.
Brinkman Dirk
Curan Andrew J.
Dodds, Jr. Harold E.
Mitsubishi Electric Research Laboratories Inc.
Robinson Greta
LandOfFree
Method for traversing quadtrees, octrees, and N-dimensional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for traversing quadtrees, octrees, and N-dimensional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for traversing quadtrees, octrees, and N-dimensional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3413654