Hanan SametHanan Samet, the 2022 Pierre Bézier Award Recipient
- Personal Website: http://www.cs.umd.edu/~hjs/
Hanan Samet pioneered the use of spatial indexing methods such as quadtrees and octrees in image processing and computer graphics with subsequent deployment in solid modeling applications. These methods are based on sorting the data with respect to the space that they occupy. Sorting speeds up the algorithms that operate on the data as they all invariably involve search which is pruned by the sort. His work interprets “sorting” as a differentiation rather than as an ordering process. The result is an implicit sort rather than an explicit sort, as the ordering notion does not exist in dimensions greater than one. Today, quadtrees, octrees, and their variants using bounding box hierarchies are used in a wide range of applications including reservoir modeling, medicine, robotics, and transportation. Much of his work is captured in his three foundational books and has led to his being called “the dean of spatial indexing” (Jim Gray).
Hanan’s 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 blocks’ 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 focus of his work was on 2D data, the application to 3D 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 consisting of collections of vertices and edges called PM quadtrees (CVPR 1983 and ACM TODS 1985) which were also developed by others for 3D data (e.g., PM octrees, among others) where the difference from the 2D case is the additional face primitive in the collection. He showed (SIGGRAPH 1986) how to implement these representations so that the data structure could represent the objects exactly without worrying about how to reconstruct the objects or the results of the operations on the original data. He also developed (SIGGRAPH 1986) a probabilistic version of these data structures called PMR quadtrees and octrees, 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 2-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 data structures is that the storage requirements are proportional to the number of edges in the object (SIAM Journal on Computing, 2005). He has also developed an incremental nearest neighbor finding algorithm (SSD 1995 and ACM TODS 1999) which is useful in many applications which require knowledge of neighboring objects and one does not know in advance how many are needed. This is useful in applications such as collision detection and forms the heart of the SIFT method in computer vision.
His multidimensional and metric data structures book received an award in the 2006 best book in Computer and Information Science competition from the Professional and Scholarly Publishers (PSP) of the American Publishers Association (AAP). Other awards include the 2009 UCGIS Research Award, the 2011 ACM Paris Kanellakis Theory and Practice Award and the 2014 IEEE Computer Society Wallace McDowell Award, as well as being an ACM, IEEE, IAPR, AAAS, and UCGIS Fellow, an SMA Pioneer, and a member of the SIGGRAPH Academy. He is the Founding Chair of the ACM Special Interest Group on Spatial Data (SIGSPATIAL) and the Founding Editor-in-Chief of ACM Transactions on Spatial Algorithms and Systems (TSAS).