| Data structures used for multi-dimensional or spatial data. Topics include (1) point data structures (e.g. k-d tree; point, MX and PR quadtrees; range tree; bucket methods), (2) 2D boundary/vector data structures (e.g. strip tree; R-tree; PM and MX-CIF quadtrees; doubly connected edge list), (3) 2D raster representations (e.g. 2D run-length encoding, region quadtrees, linear quadtrees), (4) 3D data structures for surfaces and solids (e.g. winged-edge structures, BSP tree octrees, constructive solid geometry). A formal course in Data Structures (e.g. CS3323 or permission of the instructor is required as a prerequisite. |
