Mehlhorn, Kurt Data structures and algorithms 3: Multi-dimensional searching and computational geometry. Transl. from the German. (English) Zbl 0556.68003 EATCS. Monographs on Theoretical Computer Science, 3. Berlin etc.: Springer-Verlag. XII, 284 p. DM 48.00 (1984). 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 Cited in 6 ReviewsCited in 71 Documents 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 Keywords:match queries; trees; intersection problems; convex hull; closest point; polygons Citations:Zbl 0357.68041; Zbl 0556.68002 PDFBibTeX XML