Sorting in Space: Multidimensional, Spatial, and Metric Data Structures for Computer Graphics Applications
3:45 - 5:30 pm
Room 515 A
Theme: Complexity and Accessibility
Representation of spatial data is an important issue in game programming, computer graphics, visualization, solid modeling, computer vision, and geographic-information systems (GIS). Recent interest in this field has focues on hierarchical data structures such as quadtrees, octrees, and pyramids, which are based on image hierarchies, and methods that make use of bounding boxes, which are based on object hierarchies. The key advantage of these approaches is that they provide a way to index into space. In fact, they are little more than multidimensional sorts. They are compact. Depending on the nature of the spatial data, they save space and time. And they facilitate operations such as search.
This class describes hierarchical representations of points, lines, collections of small rectangles, regions, surfaces, and volumes. For region data, the class emphasizes the dimension-reduction property of the region quadtree and octree. It also demonstrates how to use them 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. The VASCO JAVA applet is presented to illustrate these methods.
Familiarity with computer terminology and some programming experience.
University of Maryland
Hanan Samet is a professor of computer science at the University of Maryland, where he researches the use of hierarchical data structures for GIS, spatial databases, and image databases. He is the author of the recent book Foundations of Multidimensional and Metric Data Structures (Morgan-Kaufmann, 2006) and the first two texts in the field: Design and Analysis of Spatial Data Structures and Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS. He has a PhD from Stanford University, and he is a Fellow of the ACM, IEEE, and the International Association of Pattern Recognition (IAPR).