Computer Graphics |

Reading |

Computational Geometry: Algorithms and Applications

Second Edition

Mark de Berg, Marc van Kreveld, Mark Overmars, Utrecht (the Netherlands)

Otfried Schwarzkopf, Hong Kong (China)

Springer Verlag (2000)

ISBN 3-540-65620-0

List Price : 32,95 €

Contents

Computational Geometry: Introduction : An Example: Convex Hulls . - Degeneracies and Robustness. - Application Domains

Line Segment Intersection: Thematic Map Overlay: Line Segment Intersection. - The Doubly-Connected Edge List. - Computing the Overlay of Two Subdivisions. - Boolean Operations

Polygon Triangulation: Guarding an Art Gallery: Guarding and Triangulations. - Partitioning a Polygon into Monotone Pieces. - Triangulating a Monotone Polygon

Linear Programming: Manufacturing with Molds: The Geometry of Casting. - Half-Plane Intersection. - Incremental Linear Programming. - Randomised Linear Programming. - Unbounded Linear Programs. - Linear Programming in Higher Dimensions. - Smallest Enclosing Discs

Orthogonal Range Searching: Querying a Database: Dimensional Range Searching. - Kd-Trees. - Range Trees. - Higher-Dimensional Range Trees. - General Sets of Points. - Fractional Cascading

Point Location: Knowing Where You Are: Point Location and Trapezoidal Maps. - A Randomised Incremental Algorithm. - Dealing with Degenerate Cases. - A Tail Estimate

Voronoi Diagrams: The Post Office Problem: Definition and Basic Properties. - Computing the Voronoi Diagram

Arrangements and Duality: Supersampling in Ray Tracing: Computing the Discrepancy. - Duality. - Arrangements of Lines. - Levels and Discrepancy

Delaunay Triangulations: Height Interpolation: Triangulations of Planar Point Sets. - The Delaunay Triangulation. - Computing the Delaunay Triangulation. - The Analysis. - A Framework for Randomised Algorithms

More Geometric Data Structures: Windowing: Interval Trees. - Priority Search Trees. - Segment Trees

Convex Hulls: Mixing Things: The Complexity of Convex Hulls in -Space. - Computing Convex Hulls in -Space. - The Analysis. - Convex Hulls and Half-Space Intersection. - Voronoi Diagrams Revisited

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

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

Quad Trees: Non-Uniform Mesh Generation: Uniform and Non-Uniform Meshes. - Quad Trees for Point Sets. - From Quad Trees to Meshes

Visibility Graphs: Finding the Shortest Route: Shortest Paths for a Point Robot. - Computing the Visibility Graph. - Shortest Paths for a Translating Polygonal RobotSimplex

Range Searching: Windowing Revisited: Partition Trees. - Multi-Level Partition Trees . - Cutting Trees