Hierarchical data structures and algorithms for computer graphics. I. Fundamentals

Author

Samet, H. ; Webber, R.E.

Author_Institution

Dept. of Comput. Sci., Maryland Univ., College Park, MD, USA

Volume

8

Issue

3

fYear

1988

fDate

5/1/1988 12:00:00 AM

Firstpage

48

Lastpage

68

Abstract

The fundamentals of hierarchical data structures are reviewed and it is shown how they are used in the implementation of some basic operations in computer graphics. The properties of hierarchical structures are discussed, focusing on quadtrees and octrees. The latter are defined, some of the more common ways in which they are implemented are examined, and an explanation of the quadtree/octree complexity theorem is provided. Vector quadtrees and vector octrees are discussed. The performance of basic operations using quadtrees is considered.<>

Keywords

computational complexity; computer graphics; data structures; complexity theorem; computer graphics; hierarchical data structures; octrees; quadtrees; Application software; Computer displays; Computer graphics; Data structures; Image segmentation; Large-scale systems; Layout; Pixel; Rendering (computer graphics); Solid modeling; Adult; Aged; Anti-Inflammatory Agents, Non-Steroidal; Biological Markers; Chemokine CCL2; Creatinine; Cross-Over Studies; Female; Humans; Indomethacin; Kidney Failure, Chronic; Male; Middle Aged; Nephritis; Prospective Studies; Proteinuria;

fLanguage

English

Journal_Title

Computer Graphics and Applications, IEEE

Publisher

ieee

ISSN

0272-1716

Type

jour

DOI

10.1109/38.513

Filename

513