Skip to content

Computational Geometry : Algorithms and Applications

Best in textbook rentals since 2012!

ISBN-10: 354061270X

ISBN-13: 9783540612704

Edition: 1st 1997

Authors: Mark de Berg

List price: $34.95
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!


This all-new introduction to computational geometry is a textbook for high-level undergraduate and low-level graduate courses. The focus is on algorithms and hence the book is well suited for students in computer science and engineering. Motivation is provided from the application areas: all solutions and techniques of computational geometry are related to particular applications in robotics, graphics, CAD/CAM, and geographic information systems. For students this motivation will be especially welcome. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement. All the basic techniques and topics from computational…    
Customers also bought

Book details

List price: $34.95
Edition: 1st
Copyright year: 1997
Publisher: Springer
Binding: Hardcover
Size: 6.10" wide x 9.25" long x 0.42" tall
Weight: 0.880
Language: English

Computational Geometry
An Example: Convex Hulls
Degeneracies and Robustness
Application Domains
Notes and Comments
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
Polygon Triangulation
Guarding an Art Gallery
Guarding and Triangulations
Partitioning a Polygon into Monotone Pieces
Triangulating a Monotone Polygon
Notes and Comments
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
Orthogonal Range Searching
Querying a Database
1-Dimensional Range Searching
Range Trees
Higher-Dimensional Range Trees
General Sets ofPoints
Fractional Cascading
Notes and Comments
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
Voronoi Diagrams
The Post Office Problem
Definition and Basic Properties
Computing the Voronoi Diagram
Notes and Comments
Arrangements and Duality
Supersampling in Ray Tracing
Computing the Discrepancy
Arrangements of Lines
Levels and Discrepancy
Notes and Comments
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
More Geometric Data Structures
Interval Trees
Priority Search Trees
Segment Trees
Notes and Comments
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
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
Notes and Comments
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
Non-Uniform Mesh Generation
Uniform and Non-Uniform Meshes
Quadtrees for Point Sets
From Quadtrees to Meshes
Notes and Comments
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
Simplex Range Searching
Windowing Revisited
Partition Trees
Multi-Level Partition Trees
Cutting Trees
Notes and Comments