Browse Books

Reviewer: A. T. Campbell

This two-volume series is an effort to provide a guide to the study of hierarchical data structures. The topic has extensive influence on many fields, particularly computer graphics, image processing, and computational geometry. Hanan Samet is a well-established expert in the field, with dozens of publications to his name. As a computer graphics researcher, I eagerly anticipated the books' publication. A close examination of both volumes leads to one conclusion: the books are worthwhile. The integration of diverse material is notable. Comprehensive research results throughout the spectrum of science are drawn together seamlessly. Samet has done a thorough job of pulling together literature from a vast collection of conference proceedings and journals, both major and minor. The level of explanation is good. The descriptions of algorithms reflect an understanding of what is really going on. Even algorithms mentioned briefly are given a good essential description. The books include algorithms for such problems as proximity searching, efficient storage of image and volume data, constructive solid geometry, data structure conversion, hidden surface removal, and ray tracing. Pseudo-ALGOL code examples present detailed explanations of how to build and traverse many of the data structures. Ray tracing enthusiasts in particular will enjoy a detailed description of how to trace a path through an octree. There are, however, a few problems with the presentation. Despite the ambitious titles of the volumes, they contain nowhere near as much theory or practical advice as one might expect. Instead, the emphasis is on explaining literally everything at an understandable level. While this makes the books a wonderful introduction to spatial data structures, the reader will need additional guidance in choosing what techniques to actually use. The title of the first volume, The design and analysis of spatial data structures , obviously invites comparison with the classic text, The design and analysis of computer algorithms , by Aho, Hopcroft, and Ullman [1]. Samet's approach differs greatly from that of Aho et al., however. While he describes and discusses the data structures in detail, the analysis is not very formal. Theorems and proofs, as well as detailed algorithm analyses, are not much in evidence. A more appropriate title might be simply An introduction to spatial data structures . The second book covers basically every research result in hierarchical algorithms, major and minor. It is especially good at explaining techniques succinctly. The reader will find that the depth of explanation is not sufficient to help her or him implement the techniques, and will need to refer to the original papers, however. Additionally, I do not get a good feel for which results should actually be used. Samet never indicates whether a technique is commonly used in industry or never used because of its impracticality. The reader who expects a “cookbook” solution to a problem will be disappointed. The books are primarily of use for two purposes. First, they provide a good introduction to those aspects of computation geometry and image processing which are most likely to be of interest to a person working in graphics. Second, they provide a complete guidebook to the literature. I recommend that researchers and practitioners have these volumes on their reference shelves. Due to the sheer volume of material they present, however, I do not recommend them for use as course textbooks.