| Computational Geometry | p. 1 |
| Introduction | |
| An Example: Convex Hulls | p. 2 |
| Degeneracies and Robustness | p. 8 |
| Application Domains | p. 10 |
| Notes and Comments | p. 13 |
| Exercises | p. 15 |
| Line Segment Intersection | p. 19 |
| Thematic Map Overlay | |
| Line Segment Intersection | p. 20 |
| The Doubly‐Connected Edge List | p. 29 |
| Computing the Overlay of Two Subdivisions | p. 33 |
| Boolean Operations | p. 39 |
| Notes and Comments | p. 40 |
| Exercises | p. 41 |
| Polygon Triangulation | p. 45 |
| Guarding an Art Gallery | |
| Guarding and Triangulations | p. 46 |
| Partitioning a Polygon into Monotone Pieces | p. 49 |
| Triangulating a Monotone Polygon | p. 55 |
| Notes and Comments | p. 59 |
| Exercises | p. 60 |
| Linear Programming | p. 63 |
| Manufacturing with Molds | |
| The Geometry of Casting | p. 64 |
| Half‐Plane Intersection | p. 66 |
| Incremental Linear Programming | p. 71 |
| Randomized Linear Programming | p. 76 |
| Unbounded Linear Programs | p. 79 |
| Linear Programming in Higher Dimensions | p. 82 |
| Smallest Enclosing Discs | p. 86 |
| Notes and Comments | p. 89 |
| Exercises | p. 91 |
| Orthogonal Range Searching | p. 95 |
| Querying a Database | |
| 1‐Dimensional Range Searching | p. 96 |
| Kd‐Trees | p. 99 |
| Range Trees | p. 105 |
| Higher‐Dimensional Range Trees | p. 109 |
| General Sets of Points | p. 110 |
| Fractional Cascading | p. 111 |
| Notes and Comments | p. 115 |
| Exercises | p. 117 |
| Point Location | p. 121 |
| Knowing Where You Are | |
| Point Location and Trapezoidal Maps | p. 122 |
| A Randomized Incremental Algorithm | p. 128 |
| Dealing with Degenerate Cases | p. 137 |
| A Tail Estimate | p. 140 |
| Notes and Comments | p. 143 |
| Exercises | p. 144 |
| Voronoi Diagrams | p. 147 |
| The Post Office Problem | |
| Definition and Basic Properties | p. 148 |
| Computing the Voronoi Diagram | p. 151 |
| Voronoi Diagrams of Line Segments | p. 160 |
| Farthest‐Point Voronoi Diagrams | p. 163 |
| Notes and Comments | p. 167 |
| Exercises | p. 170 |
| Arrangements and Duality | p. 173 |
| Supersampling in Ray Tracing | |
| Computing the Discrepancy | p. 175 |
| Duality | p. 177 |
| Arrangements ofLines | p. 179 |
| Levels and Discrepancy | p. 185 |
| Notes and Comments | p. 186 |
| Exercises | p. 188 |
| Delaunay Triangulations | p. 191 |
| Height Interpolation | |
| Triangulations of Planar Point Sets | p. 193 |
| The Delaunay Triangulation | p. 196 |
| Computing the Delaunay Triangulation | p. 199 |
| The Analysis | p. 205 |
| A Framework for Randomized Algorithms | p. 208 |
| Notes and Comments | p. 214 |
| Exercises | p. 215 |
| More Geometric Data Structures | p. 219 |
| Windowing | |
| Interval Trees | p. 220 |
| Priority Search Trees | p. 226 |
| Segment Trees | p. 231 |
| Notes and Comments | p. 237 |
| Exercises | p. 239 |
| Convex Hulls | p. 243 |
| Mixing Things | |
| The Complexity of Convex Hulls in 3‐Space | p. 244 |
| Computing Convex Hulls in 3‐Space | p. 246 |
| The Analysis | p. 250 |
| Convex Hulls and Half‐Space Intersection | p. 253 |
| Voronoi Diagrams Revisited | p. 254 |
| Notes and Comments | p. 256 |
| Exercises | p. 257 |
| Binary Space Partitions | p. 259 |
| The Painter's Algorithm | |
| The Definition of BSP Trees | p. 261 |
| BSP Trees and the Painter's Algorithm | p. 263 |
| Constructing a BSP Tree | p. 264 |
| The Size ofBSP Trees in 3‐Space | p. 268 |
| BSP Trees for Low‐Density Scenes | p. 271 |
| Notes and Comments | p. 278 |
| Exercises | p. 279 |
| Robot Motion Planning | p. 283 |
| Getting Where You Want to Be | |
| Work Space and Configuration Space | p. 284 |
| A Point Robot | p. 286 |
| Minkowski Sums | p. 290 |
| Translational Motion Planning | p. 297 |
| Motion Planning with Rotations | p. 299 |
| Notes and Comments | p. 303 |
| Exercises | p. 305 |
| Quadtrees | p. 307 |
| Non‐Uniform Mesh Generation | |
| Uniform and Non‐Uniform Meshes | p. 308 |
| Quadtrees forPoint Sets | p. 309 |
| From Quadtrees to Meshes | p. 315 |
| Notes and Comments | p. 318 |
| Exercises | p. 320 |
| Visibility Graphs | p. 323 |
| Finding the Shortest Route | |
| Shortest Paths fora Point Robot | p. 324 |
| Computing the Visibility Graph | p. 326 |
| Shortest Paths for a Translating Polygonal Robot | p. 330 |
| Notes and Comments | p. 331 |
| Exercises | p. 332 |
| Simplex Range Searching | p. 335 |
| Windowing Revisited | |
| Partition Trees | p. 336 |
| Multi‐Level Partition Trees | p. 343 |
| Cutting Trees | p. 346 |
| Notes and Comments | p. 352 |
| Exercises | p. 353 |
| Bibliography | p. 357 |
| Index | p. 377 |
| Table of Contents provided by Publisher. All Rights Reserved. |