Computational Geometry : An Introduction

From the reviews: "This book offers a coherent treatment, at the graduate textbook level, of the field that has come to be known in the last decade or so as computational geometry. ... ... The book is well organized and lucidly written; a timely contribution by two founders of the field. It clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics. It also points the way to the solution of the more challenging problems in dimensions higher than two." #Mathematical Reviews#1 "... This remarkable book is a comprehensive and systematic study on research results obtained especially in the last ten years. The very clear presentation concentrates on basic ideas, fundamental combinatorial structures, and crucial algorithmic techniques. The plenty of results is clever organized following these guidelines and within the framework of some detailed case studies. A large number of figures and examples also aid the understanding of the material. Therefore, it can be highly recommended as an early graduate text but it should prove also to be essential to researchers and professionals in applied fields of computer-aided design, computer graphics, and robotics." #Biometrical Journal#2

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.