**1 Computational Geometry**--- Introduction- 1.1 An Example: Convex Hulls
- 1.2 Degeneracies and Robustness
- 1.3 Application Domains
- 1.4 Notes and Comments
- 1.5 Exercises
**2 Line Segment Intersection**--- Thematic Map Overlay- 2.1 Line Segment Intersection
- 2.2 The Doubly-Connected Edge List
- 2.3 Computing the Overlay of Two Subdivisions
- 2.4 Boolean Operations
- 2.5 Notes and Comments
- 2.6 Exercises
**3 Polygon Triangulation**--- Guarding an Art Gallery- 3.1 Guarding and Triangulations
- 3.2 Partitioning a Polygon into Monotone Pieces
- 3.3 Triangulating a Monotone Polygon
- 3.4 Notes and Comments
- 3.5 Exercises
**4 Linear Programming**--- Manufacturing with Molds- 4.1 The Geometry of Casting
- 4.2 Half-Plane Intersection
- 4.3 Incremental Linear Programming
- 4.4 Randomized Linear Programming
- 4.5 Unbounded Linear Programs
- 4.6* Linear Programming in Higher Dimensions
- 4.7* Smallest Enclosing Discs
- 4.8 Notes and Comments
- 4.9 Exercises
**5 Orthogonal Range Searching**--- Querying a Database- 5.1 1-Dimensional Range Searching
- 5.2 Kd-Trees
- 5.3 Range Trees
- 5.4 Higher-Dimensional Range Trees
- 5.5 General Sets of Points
- 5.6* Fractional Cascading
- 5.7 Notes and Comments
- 5.8 Exercises
**6 Point Location**--- Knowing Where You Are- 6.1 Point Location and Trapezoidal Maps
- 6.2 A Randomized Incremental Algorithm
- 6.3 Dealing with Degenerate Cases
- 6.4* A Tail Estimate
- 6.5 Notes and Comments
- 6.6 Exercises
**7 Voronoi Diagrams**--- The Post Office Problem- 7.1 Definition and Basic Properties
- 7.2 Computing the Voronoi Diagram
- 7.3 Voronoi Diagrams of Line Segments
- 7.4 Farthest-Point Voronoi Diagrams
- 7.5 Notes and Comments
- 7.6 Exercises
**8 Arrangements and Duality**--- Supersampling in Ray Tracing- 8.1 Computing the Discrepancy
- 8.2 Duality
- 8.3 Arrangements of Lines
- 8.4 Levels and Discrepancy
- 8.5 Notes and Comments
- 8.6 Exercises
**9 Delaunay Triangulations**--- Height Interpolation- 9.1 Triangulations of Planar Point Sets
- 9.2 The Delaunay Triangulation
- 9.3 Computing the Delaunay Triangulation
- 9.4 The Analysis
- 9.5* A Framework for Randomized Algorithms
- 9.6 Notes and Comments
- 9.7 Exercises
**10 More Geometric Data Structures**--- Windowing- 10.1 Interval Trees
- 10.2 Priority Search Trees
- 10.3 Segment Trees
- 10.4 Notes and Comments
- 10.5 Exercises
**11 Convex Hulls**--- Mixing Things- 11.1 The Complexity of Convex Hulls in 3-Space
- 11.2 Computing Convex Hulls in 3-Space
- 11.3* The Analysis
- 11.4* Convex Hulls and Half-Space Intersection
- 11.5* Voronoi Diagrams Revisited
- 11.6 Notes and Comments
- 11.7 Exercises
**12 Binary Space Partitions**--- The Painter's Algorithm- 12.1 The Definition of BSP Trees
- 12.2 BSP Trees and the Painter's Algorithm
- 12.3 Constructing a BSP Tree
- 12.4* The Size of BSP Trees in 3-Space
- 12.5 BSP Trees for Low-Density Scenes
- 12.6 Notes and Comments
- 12.7 Exercises
**13 Robot Motion Planning**--- Getting Where You Want To Be- 13.1 Work Space and Configuration Space
- 13.2 A Point Robot
- 13.3 Minkowski Sums
- 13.4 Translational Motion Planning
- 13.5* Motion Planning with Rotations
- 13.6 Notes and Comments
- 13.7 Exercises
**14 Quad Trees**--- Non-Uniform Mesh Generation- 14.1 Uniform and Non-Uniform Meshes
- 14.2 Quad Trees for Point Sets
- 14.3 From Quad Trees to Meshes
- 14.4 Notes and Comments
- 14.5 Exercises
**15 Visibility Graphs**--- Finding the Shortest Route- 15.1 Shortest Paths for a Point Robot
- 15.2 Computing the Visibility Graph
- 15.3 Shortest Paths for a Translating Polygonal Robot
- 15.4 Notes and Comments
- 15.5 Exercises
**16 Simplex Range Searching**--- Windowing Revisited- 16.1 Partition Trees
- 16.2 Multi-Level Partition Trees
- 16.3 Cutting Trees
- 16.4 Notes and Comments
- 16.5 Exercises