×

Data structures and algorithms 3: Multi-dimensional searching and computational geometry. Transl. from the German. (English) Zbl 0556.68003

This last volume of the three volume monograph on data structures and algorithms covers very recent material. Most of the topics discussed appear the first time in book form. The volume can be highly recommended to researchers interested in multi-dimensional search methods and computational geometry and its applications to database systems and computer graphics.
In the part on multi-dimensional searching exact match queries, partial match queries, orthogonal match queries, and polygon queries are treated using data structures like d-dimensional trees, range trees, and polygon trees. Also multi-dimensional divide-and-conquer techniques are applied.
Efficient algorithms for intersection problems, the convex hull problem, and closest point problems, as well as methods to deal with objects whose sides are parallel to the axes and with polygons are discussed.
Reviewer: P.Brucker

MSC:

68-02 Research exposition (monographs, survey articles) pertaining to computer science
68W99 Algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
68P10 Searching and sorting
68R99 Discrete mathematics in relation to computer science