Hanan SametHanan Samet, the 2021 SMA Pioneer Award Recipient
- 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 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 which has led to his being called “the dean of spatial indexing” (Jim Gray).
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.
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) Group of the American Publishers Association (AAP). Other awards include the 2011 ACM Paris Kanellakis Theory and Practice Award and the 2014 IEEE Computer Society Wallace McDowell Award as well as being an ACM and IEEE Fellow 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).