Computational Geometry

1 Introduction.- 1.1 Historical Perspective.- 1.2 Algorithmic Background.- 1.3 Geometric Preliminaries.- 1.4 Models of Computation.- 2 Geometric Searching.- 2.1 Introduction to Geometric Searching.- 2.2 Point-Location Problems.- 2.3 Range-Searching Problems.- 2.4 Iterated Search and Fractional Cascading.- 2.5 Notes and Comments.- 2.6 Exercises.- 3 Convex Hulls: Basic Algorithms.- 3.1 Preliminaries.- 3.2 Problem Statement and Lower Bounds.- 3.3 Convex Hull Algorithms in the Plane.- 3.4 Convex Hulls in More Than Two Dimensions.- 3.5 Notes and Comments.- 3.6 Exercises.- 4 Convex Hulls: Extensions and Applications.- 4.1 Extensions and Variants.- 4.2 Applications to Statistics.- 4.3 Notes and Comments.- 4.4 Exercises.- 5 Proximity: Fundamental Algorithms.- 5.1 A Collection of Problems.- 5.2 A Computational Prototype: Element Uniqueness.- 5.3 Lower Bounds.- 5.4 The Closest Pair Problem: A Divide-and-Conquer Approach.- 5.5 The Locus Approach to Proximity Problems: The Voronoi Diagram.- 5.6 Proximity Problems Solved by the Voronoi Diagram.- 5.7 Notes and Comments.- 5.8 Exercises.- 6 Proximity: Variants and Generalizations.- 6.1 Euclidean Minimum Spanning Trees.- 6.2 Planar Triangulations.- 6.3 Generalizations of the Voronoi Diagram.- 6.4 Gaps and Covers.- 6.5 Notes and Comments.- 6.6 Exercises.- 7 Intersections.- 7.1 A Sample of Applications.- 7.2 Planar Applications.- 7.3 Three-Dimensional Applications.- 7.4 Notes and Comments.- 7.5 Exercises.- 8 The Geometry of Rectangles.- 8.1 Some Applications of the Geometry of Rectangles.- 8.2 Domain of Validity of the Results.- 8.3 General Considerations on Static-Mode Algorithms.- 8.4 Measure and Perimeter of a Union of Rectangles.- 8.5 The Contour of a Union of Rectangles.- 8.6 The Closure of a Union of Rectangles.- 8.7 The External Contour of a Union of Rectangles.- 8.8 Intersections of Rectangles and Related Problems.- 8.9 Notes and Comments.- 8.10 Exercises.- References.- Author Index.