Contents

Computational Geometry: Introduction : An Example: Convex Hulls . - Degeneracies and Robustness. - Application Domains
Line Segment Intersection: Thematic Map Overlay: Line Segment Intersection. - The Doubly-Connected Edge List. - Computing the Overlay of Two Subdivisions. - Boolean Operations
Polygon Triangulation: Guarding an Art Gallery: Guarding and Triangulations. - Partitioning a Polygon into Monotone Pieces. - Triangulating a Monotone Polygon
Linear Programming: Manufacturing with Molds: The Geometry of Casting. - Half-Plane Intersection. - Incremental Linear Programming. - Randomised Linear Programming. - Unbounded Linear Programs. - Linear Programming in Higher Dimensions. - Smallest Enclosing Discs
Orthogonal Range Searching: Querying a Database: Dimensional Range Searching. - Kd-Trees. - Range Trees. - Higher-Dimensional Range Trees. - General Sets of Points. - Fractional Cascading
Point Location: Knowing Where You Are: Point Location and Trapezoidal Maps. - A Randomised Incremental Algorithm. - Dealing with Degenerate Cases. - A Tail Estimate
Voronoi Diagrams: The Post Office Problem: Definition and Basic Properties. - Computing the Voronoi Diagram
Arrangements and Duality: Supersampling in Ray Tracing: Computing the Discrepancy. - Duality. - Arrangements of Lines. - Levels and Discrepancy
Delaunay Triangulations: Height Interpolation: Triangulations of Planar Point Sets. - The Delaunay Triangulation. - Computing the Delaunay Triangulation. - The Analysis. - A Framework for Randomised Algorithms
More Geometric Data Structures: Windowing: Interval Trees. - Priority Search Trees. - Segment Trees
Convex Hulls: Mixing Things: The Complexity of Convex Hulls in -Space. - Computing Convex Hulls in -Space. - The Analysis. - Convex Hulls and Half-Space Intersection. - Voronoi Diagrams Revisited
Binary Space Partitions: The Painter's Algorithm: The Definition of BSP Trees. - BSP Trees and the Painter's Algorithm. - Constructing a BSP Tree. - The Size of BSP Trees in 3-Space
Robot Motion Planning: Getting Where You Want To Be: Work Space and Configuration Space. - A Point Robot. - Minkowski Sums. - Translational Motion Planning. - Motion Planning with Rotations
Quad Trees: Non-Uniform Mesh Generation: Uniform and Non-Uniform Meshes. - Quad Trees for Point Sets. - From Quad Trees to Meshes
Visibility Graphs: Finding the Shortest Route: Shortest Paths for a Point Robot. - Computing the Visibility Graph. - Shortest Paths for a Translating Polygonal RobotSimplex
Range Searching: Windowing Revisited: Partition Trees. - Multi-Level Partition Trees . - Cutting Trees