Wednesday, 15 December | 9:00 AM - 10:45 AM | Room 308A

Presented in English / 영어로 발표 됨

Sorting in Space: Multidimensional, Spatial, and Metric Data Structures for Graphics Applications

Tuesday, 14 December | 7:00 pm - 8:45 pm | Room 308A

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.



Intended Audience

Computer graphics practitioners, game developers, and technical managers.

Presentation Language

Presented in English / 영어로 발표 됨


Familiarity with computer terminology and some programming experience.






Bounding-Box Hierarchies


Surfaces and Volumes

Metric Data




Hanan Samet
University of Maryland

Instructor Bios

Hanan Samet
Hanan Samet is a professor of computer science at the University of Maryland, where he researches hierarchical data structures for GIS and spatial databases. He wrote Foundations of Multidimensional and Metric Data Structures (Morgan-Kaufmann, San Francisco, CA, 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. His Ph.D is from Stanford University. He is founding chair of ACM SIGSPATIAL; a fellow of ACM, IEEE, and IAPR; and winner of the 2009 UCGIS Research Award.