Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry

Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry

by K. Mehlhorn

Paperback(Softcover reprint of the original 1st ed. 1984)

View All Available Formats & Editions
Choose Expedited Shipping at checkout for guaranteed delivery by Wednesday, May 1

Product Details

ISBN-13: 9783642699023
Publisher: Springer Berlin Heidelberg
Publication date: 01/25/2012
Series: Monographs in Theoretical Computer Science. An EATCS Series , #3
Edition description: Softcover reprint of the original 1st ed. 1984
Pages: 284
Product dimensions: 6.69(w) x 9.61(h) x 0.03(d)

Table of Contents

VII. Multidimensional Data Structures.- 1. A Black Box Approach to Data Structures.- 1.1 Dynamization.- 1.2 Weighting and Weighted Dynamization.- 1.3 Order Decomposable Problems.- 2. Multi-dimensional Searching Problems.- 2.1 D-dimensional Trees and Polygon Trees.- 2.2 Range Trees and Multidimensional Divide and Conquer.- 2.3 Lower Bounds.- 2.3.1 Partial MatchRetrieval in Minimum Space.- 2.3.2 The Spanning Bound.- 3. Exercises.- 4. Bibliographic Notes.- VIII. Computational Geometry.- 1. Convex Polygons.- 2. Convex Hulls.- 3. Voronoi Diagrams and Searching Planar Subdivisions.- 3.1 Voronoi Diagrams.- 3.2 Searching Planar Subdivisions.- 3.2.1 Removal of Large Independent Sets.- 3.2.2 Path Decompositions.- 3.2.3 Searching Dynamic Planar Subdivisions.- 3.3 Applications.- 4. The Sweep Paradigm.- 4.1 Intersection of Line Segments and Other Intersection Problems in the Plane.- 4.2 Triangulation and its Applications.- 4.3 Space Sweep.- 5. The Realm of Orthogonal Objects.- 5.1 Plane Sweep for Iso-Oriented Objects.- 5.1.1 The Interval Tree and its Applications.- 5.1.2 The Priority Search Tree and its Applications.- 5.1.3 Segment Trees.- 5.1.4 Path Decomposition and Plane Sweep for Non-Iso-Oriented Objects.- 5.2 Divide and Conquer on Iso-Oriented Objects.- 5.2.1 The Line Segment Intersection Problem.- 5.2.2 The Measure and Contour Problems.- 5.3 Intersection Problems in Higher-Dimensional Space.- 6. Geometric Transforms.- 6.1 Duality.- 6.2 Inversion.- 7. Exercises.- 8. Bibliographic Notes.- IX. Algorithmic Paradigms.

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews