Description: 1 Introduction.- 1.1 Historical Perspective.- 1.1.1 Complexity notions in classical geometry.- 1.1.2 The theory of convex sets, metric and combinatorial geometry.- 1.1.3 Prior related work.- 1.1.4 Toward computational geometry.- 1.2 Algorithmic Background.- 1.2.1 Algorithms: Their expression and performance evaluation.- 1.2.2 Some considerations on general algorithmic techniques.- 1.2.3 Data structures.- 1.2.3.1 The segment tree.- 1.2.3.2 The doubly-connected-edge-list (DCEL).- 1.3 Geometric Preliminaries.- 1.3.1 General definitions and notations.- 1.3.2 Invariants under groups of linear transformations.- 1.3.3 Geometry duality. Polarity.- 1.4 Models of Computation.- 2 Geometric Searching.- 2.1 Introduction to Geometric Searching.- 2.2 Point-Location Problems.- 2.2.1 General considerations. Simple cases.- 2.2.2 Location of a point in a planar subdivision.- 2.2.2.1 The slab method.- 2.2.2.2 The chain method.- 2.2.2.3 Optimal techniques: the planar-separator method, the triangulation refinement method, and the bridged chain method.- 2.2.2.4 The trapezoid method.- 2.3 Range-Searching Problems.- 2.3.1 General considerations.- 2.3.2 The method of the multidimensional binary tree (k-D tree).- 2.3.3 A direct access method and its variants.- 2.3.4 The range-tree method and its variants.- 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.3.1 Early development of a convex hull algorithm.- 3.3.2 Graham''s scan.- 3.3.3 Jarvis''s march.- 3.3.4 QUICKHULL techniques.- 3.3.5 Divide-and-conquer algorithms.- 3.3.6 Dynamic convex hull algorithms.- 3.3.7 A generalization: dynamic convex hull maintenance.- 3.4 Convex Hulls in More Than Two Dimensions.- 3.4.1 The gift-wrapping method.- 3.4.2 The beneath-beyond method.- 3.4.3 Convex hulls in three dimensions.- 3.5 Notes and Comments.- 3.6 Exercises.- 4 Convex Hulls: Extensions and Applications.- 4.1 Extensions and Variants.- 4.1.1 Average-case analysis.- 4.1.2 Approximation algorithms for convex hull.- 4.1.3 The problem of the maxima of a point set.- 4.1.4 Convex hull of a simple polygon.- 4.2 Applications to Statistics.- 4.2.1 Robust estimation.- 4.2.2 Isotonic regression.- 4.2.3 Clustering (diameter of a point set).- 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.5.1 A catalog of Voronoi properties.- 5.5.2 Constructing the Voronoi diagram.- 5.5.2.1 Constructing the dividing chain.- 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.1.1 Euclidean traveling salesman.- 6.2 Planar Triangulations.- 6.2.1 The greedy triangulation.- 6.2.2 Constrained triangulations.- 6.2.2.1 Triangulating a monotone polygon.- 6.3 Generalizations of the Voronoi Diagram.- 6.3.1. Higher-order Voronoi diagrams (in the plane).- 6.3.1.1 Elements of inversive geometry.- 6.3.1.2 The structure of higher-order Voronoi diagrams.- 6.3.1.3 Construction of the higher-order Voronoi diagrams.- 6.3.2 Multidimensional closest-point and farthest-point Voronoi diagrams.- 6.4 Gaps and Covers.- 6.5 Notes and Comments.- 6.6 Exercises.- 7 Intersections.- 7.1 A Sample of Applications.- 7.1.1 The hidden-line and hidden-surface problems.- 7.1.2 Pattern recognition.- 7.1.3 Wire and component layout.- 7.1.4 Linear programming and common intersection of half-spaces.- 7.2 Planar Applications.- 7.2.1 Intersection of convex polygons.- 7.2.2 Intersection of star-shaped polygons.- 7.2.3 Intersection of line segments.- 7.2.3.1 Applications.- 7.2.3.2 Segment intersection algorithms.- 7.2.4 Intersection of half-planes.- 7.2.5 Two-variable linear programming.- 7.2.6 Kernel of a plane polygon.- 7.3 Three-Dimensional Applications.- 7.3.1 Intersection of convex polyhedra.- 7.3.2 Intersection of half-spaces.- 7.4 Notes and Comments.- 7.5 Exercises.- 8 The Geometry of Rectangles.- 8.1 Some Applications of the Geometry of Rectangles.- 8.1.1 Aids for VLSI design.- 8.1.2 Concurrency controls in databases.- 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.8.1 Intersections of rectangles.- 8.8.2 The rectangle intersection problem revisited.- 8.8.3 Enclosure of rectangles.- 8.9 Notes and Comments.- 8.10 Exercises.- References.- Author Index.

Please Wait