Back to the index
Table of Contents
- 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