Berg Mark de et al. Computational Geometry: Algorithms and Applications

3rd edition. — Springer, 2008. — 398 p.This introduction to computational geometry focuses on algorithms. Motivation is provided from the application areas as all techniques are related to particular applications in robotics, graphics, CAD/CAM, and geographic information systems. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement.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.
itioning 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.
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 of Lines.
Levels and Discrepancy.
Notes and Comments 186 CONTENTS.
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 of BSP 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 for Point Sets.
From Quadtrees to Meshes.
Notes and Comments.
Exercises.
Visibility Graphs.
Finding the Shortest Route.
Shortest Paths for a Point Robot.
Computing the Visibility Graph.
Shortest Paths for a Translating Polygonal Robot.
Notes and Comments.
Exercises.
Simplex Range Searching.
Windowing Revisited.
ition Trees.
Multi-Level Partition Trees.
Cutting Trees.
Notes and Comments.
Exercises.