- Personal Website: http://www.cs.umd.edu/~hjs/
Hanan Samet pioneered using spatial indexing methods such as quadtrees and octrees in image processing and graphics with subsequent deployment in solid modeling applications. Today, quadtrees, octrees, and their variants are extensively used in a wide range of applications including reservoir modeling (paradigm geophysical and landmark systems), medicine, robotics, game engines, and transportation. Google Earth uses quadtrees for organizing spatial information. UPS uses quadtrees in an in-house geographical information system. Much of his work is captured in his three foundational books has led to his being called “the dean of spatial indexing” (Jim Gray). His paper on building quadtrees from chain codes (CACM 1980) sparked interest in spatial indexing.
Quadtrees and octrees are based on the recursive decomposition of images in which object collections are embedded into blocks until some predefined condition is satisfied. He showed how basic operations can be implemented as tree traversals where the operation would be applied to nodes corresponding to blocks and their neighbors. In particular, he showed how neighbors could be computed in constant time by just using the structure of the tree and without needing additional storage and in ways that are independent of knowledge of the block’s locations. The result were algorithms whose execution time is proportional to the number of blocks and not their sizes. The virtue of these data structures is that the number of blocks is proportional to the perimeter (surface area) of the 2d (3d) objects. Therefore, the data structures act like dimension reducing devices since the computational complexity of the algorithms that use them is reduced by one dimension, which is substantial when the dimension is low as is the case for quadtrees and octrees. Although the initial main focus of his work was on two-dimensional data, the application to three-dimensional data was a natural one and can be seen by his papers on the construction of octrees from boundary models (SIGGRAPH 1984) and the conversion from CSG to octrees (SIGGRAPH 1985 and Visual Computer 1990). He also wrote a fundamental paper on the representation of collections of polygonal subdivisions which consists of collections of vertices and edges called PM quadtrees (CVPR 1983 and ACM TODS 1985) which were also developed by others for three-dimensional data (PM octrees and other names) where the difference from the two-dimensional case is the additional face primitive in the collection. He showed (SIGGRAPH 1986) how to implement these representations so that the quadtree (octree) data structure could represent the objects exactly (not an approximation) without worrying about how to reconstruct the objects or the results of the operations on the original data. He also developed (SIGGRAPH 1986) the PMR quadtree (octree), a probabilistic version of this data structure, which is edge-based (face-based) in the case of quadtrees (octrees) where blocks are decomposed only once when the number of edges (faces) that they contain exceeds a predefined entity called the splitting threshold. This has the advantage of avoiding an unbounded number of block splitting operations when the number of edges meeting at a vertex exceeds the splitting threshold (not a problem in three dimensions as the number of faces meeting at an edge cannot exceed two for two-manifolds). Unboundedness results when using a bucketing approach whose only split termination condition is the number of edges or faces in a block. Another advantage of the PMR quadtree is that the storage requirements are proportional to the number of edges in the object (SIAM Journal on Computing, 2005).