Courses

Representation of spatial data is an important issue in game programming, computer graphics, visualization, solid modeling, computer vision, and geographic information systems (GIS). Recently, there has been much interest in hierarchical representations such as quadtrees, octrees, and pyramids, based on image hierarchies, as well as methods that use bounding boxes, based on object hierarchies. The key advantage of these representations is that they provide a way to index into space. In fact, they are little more than multidimensional sorts. They are compact and, depending on the nature of the spatial data, they save space and time, and facilitate operations such as search.

This course provides a brief overview of hierarchical spatial data structures and related algorithms that make use of them. It describes hierarchical representations of points, lines, collections of small rectangles, regions, surfaces, and volumes. For region data, it points out the dimension-reduction property of the region quadtree and octree, and how to navigate between nodes in the same tree, a main reason for the popularity of these representations in ray-tracing applications. The course also demonstrates how to use these representations for both raster and vector data. In the case of nonregion data, it shows how these data structures can be used to compute nearest objects in an incremental fashion so that the number of objects need not be known in advance. It also reviews a number of different tessellations and shows why hierarchical decomposition into squares instead of triangles or hexagons is preferred. The course concludes with a demonstration of the SAND spatial browser, based on the SAND spatial database system, and presentation of the VASCO JAVA applet.