| |
| |
| |
| Computational Geometry | |
| |
| |
| Introduction | |
| |
| |
| |
| An Example: Convex Hulls | |
| |
| |
| |
| Degeneracies and Robustness | |
| |
| |
| |
| Application Domains | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Line Segment Intersection | |
| |
| |
| Thematic Map Overlay | |
| |
| |
| |
| Line Segment Intersection | |
| |
| |
| |
| The Doubly‐Connected Edge List | |
| |
| |
| |
| Computing the Overlay of Two Subdivisions | |
| |
| |
| |
| Boolean Operations | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Polygon Triangulation | |
| |
| |
| Guarding an Art Gallery | |
| |
| |
| |
| Guarding and Triangulations | |
| |
| |
| |
| Partitioning a Polygon into Monotone Pieces | |
| |
| |
| |
| Triangulating a Monotone Polygon | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Linear Programming | |
| |
| |
| Manufacturing with Molds | |
| |
| |
| |
| The Geometry of Casting | |
| |
| |
| |
| Half‐Plane Intersection | |
| |
| |
| |
| Incremental Linear Programming | |
| |
| |
| |
| Randomized Linear Programming | |
| |
| |
| |
| Unbounded Linear Programs | |
| |
| |
| |
| Linear Programming in Higher Dimensions | |
| |
| |
| |
| Smallest Enclosing Discs | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Orthogonal Range Searching | |
| |
| |
| Querying a Database | |
| |
| |
| |
| 1‐Dimensional Range Searching | |
| |
| |
| |
| Kd‐Trees | |
| |
| |
| |
| Range Trees | |
| |
| |
| |
| Higher‐Dimensional Range Trees | |
| |
| |
| |
| General Sets of Points | |
| |
| |
| |
| Fractional Cascading | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Point Location | |
| |
| |
| Knowing Where You Are | |
| |
| |
| |
| Point Location and Trapezoidal Maps | |
| |
| |
| |
| A Randomized Incremental Algorithm | |
| |
| |
| |
| Dealing with Degenerate Cases | |
| |
| |
| |
| A Tail Estimate | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Voronoi Diagrams | |
| |
| |
| The Post Office Problem | |
| |
| |
| |
| Definition and Basic Properties | |
| |
| |
| |
| Computing the Voronoi Diagram | |
| |
| |
| |
| Voronoi Diagrams of Line Segments | |
| |
| |
| |
| Farthest‐Point Voronoi Diagrams | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Arrangements and Duality | |
| |
| |
| Supersampling in Ray Tracing | |
| |
| |
| |
| Computing the Discrepancy | |
| |
| |
| |
| Duality | |
| |
| |
| |
| Arrangements ofLines | |
| |
| |
| |
| Levels and Discrepancy | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Delaunay Triangulations | |
| |
| |
| Height Interpolation | |
| |
| |
| |
| Triangulations of Planar Point Sets | |
| |
| |
| |
| The Delaunay Triangulation | |
| |
| |
| |
| Computing the Delaunay Triangulation | |
| |
| |
| |
| The Analysis | |
| |
| |
| |
| A Framework for Randomized Algorithms | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| More Geometric Data Structures | |
| |
| |
| Windowing | |
| |
| |
| |
| Interval Trees | |
| |
| |
| |
| Priority Search Trees | |
| |
| |
| |
| Segment Trees | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Convex Hulls | |
| |
| |
| Mixing Things | |
| |
| |
| |
| The Complexity of Convex Hulls in 3‐Space | |
| |
| |
| |
| Computing Convex Hulls in 3‐Space | |
| |
| |
| |
| The Analysis | |
| |
| |
| |
| Convex Hulls and Half‐Space Intersection | |
| |
| |
| |
| Voronoi Diagrams Revisited | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| 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 ofBSP Trees in 3‐Space | |
| |
| |
| |
| BSP Trees for Low‐Density Scenes | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Quadtrees | |
| |
| |
| Non‐Uniform Mesh Generation | |
| |
| |
| |
| Uniform and Non‐Uniform Meshes | |
| |
| |
| |
| Quadtrees forPoint Sets | |
| |
| |
| |
| From Quadtrees to Meshes | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Visibility Graphs | |
| |
| |
| Finding the Shortest Route | |
| |
| |
| |
| Shortest Paths fora Point Robot | |
| |
| |
| |
| Computing the Visibility Graph | |
| |
| |
| |
| Shortest Paths for a Translating Polygonal Robot | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Simplex Range Searching | |
| |
| |
| Windowing Revisited | |
| |
| |
| |
| Partition Trees | |
| |
| |
| |
| Multi‐Level Partition Trees | |
| |
| |
| |
| Cutting Trees | |
| |
| |
| |
| Notes and Comments | |
| |
| |
| |
| Exercises | |
| |
| |
| Bibliography | |
| |
| |
| Index | |