Computational Geometry Algorithms and Applications /

• Main Authors: Berg, Mark de (Author), Cheong, Otfried (Author), Kreveld, Marc van (Author), Overmars, Mark (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg, 2008.
• Edition: Third Edition.
• Subjects: Computer science.; Earth sciences.; Computers.; Algorithms.; Computer science > Mathematics.; Computer graphics.; Geometry.; Computer Science.; Theory of Computation.; Math Applications in Computer Science.; Earth Sciences, general.; Computer Graphics.; Algorithm Analysis and Problem Complexity.

Computational geometry emerged from the ?eld of algorithms design and analysis in the late 1970s. It has grown into a recognized discipline with its own journals, conferences, and a large community of active researchers. The success of the ?eld as a research discipline can on the one hand be explain...

Table of Contents:

• Computational Geometry: Introduction
• Line Segment Intersection: Thematic Map Overlay
• Polygon Triangulation: Guarding an Art Gallery
• Linear Programming: Manufacturing with Molds
• Orthogonal Range Searching: Querying a Database
• Point Location: Knowing Where You Are
• Voronoi Diagrams: The Post Office Problem
• Arrangements and Duality: Supersampling in Ray Tracing
• Delaunay Triangulations: Height Interpolation
• More Geometric Data Structures: Windowing
• Convex Hulls: Mixing Things
• Binary Space Partitions: The Painter's Algorithm
• Robot Motion Planning: Getting Where You Want to Be
• Quadtrees: Non-Uniform Mesh Generation
• Visibility Graphs: Finding the Shortest Route
• Simplex Range Searching: Windowing Revisited
• Bibliography
• Index.