Computational Geometry: An Introduction

'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 Intersect