Computational Geometry : Algorithms and Applications

by Berg, Mark De; Kreveld, Marc Van; Overmars, Mark; Schwarzkopf, Otfried

• ISBN13: 9783540656203
• ISBN10: 3540656200
• eBook ISBN(s): 9783662042458
• Format: Hardcover
• Copyright: 2000-05-01
• Publisher: Springer Verlag
• More Book Details
• Purchase Benefits

Summary

This well-accepted 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 from 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 geometry, as well as several more advanced topics, are covered. The book is largely self-contained and can be used for self-study by anyone with a basic background in algorithms. In the second edition, besides revisions to the first edition, a number of new exercises have been added.

Table of Contents

Computational Geometry	1	(18)
Introduction
An Example: Convex Hulls	2	(6)
Degeneracies and Robustness	8	(2)
Application Domains	10	(3)
Notes and Comments	13	(2)
Exercises	15	(4)
Line Segment Intersection	19	(26)
Thematic Map Overlay
Line Segment Intersection	20	(9)
The Doubly-Connected Edge List	29	(4)
Computing the Overlay of Two Subdivisions	33	(6)
Boolean Operations	39	(1)
Notes and Comments	40	(2)
Exercises	42	(3)
Polygon Triangulation	45	(18)
Guarding an Art Gallery
Guarding and Triangulations	46	(3)
Partitioning a Polygon into Monotone Pieces	49	(6)
Triangulating a Monotone Polygon	55	(4)
Notes and Comments	59	(1)
Exercises	60	(3)
Linear Programming	63	(32)
Manufacturing with Molds
The Geometry of Casting	64	(2)
Half-Plane Intersection	66	(5)
Incremental Linear Programming	71	(6)
Randomized Linear Programming	77	(3)
Unbounded Linear Programs	80	(2)
Linear Programming in Higher Dimensions	82	(4)
Smallest Enclosing Discs	86	(4)
Notes and Comments	90	(1)
Exercises	91	(4)
Orthogonal Range Searching	95	(26)
Querying a Database
1-Dimensional Range Searching	96	(3)
Kd-Trees	99	(6)
Range Trees	105	(4)
Higher-Dimensional Range Trees	109	(2)
General Sets of Points	111	(1)
Fractional Cascading	112	(3)
Notes and Comments	115	(2)
Exercises	117	(4)
Point Location	121	(26)
Knowing Where You Are
Point Location and Trapezoidal Maps	122	(6)
A Randomized Incremental Algorithm	128	(9)
Dealing with Degenerate Cases	137	(3)
A Tail Estimate	140	(3)
Notes and Comments	143	(1)
Exercises	144	(3)
Voronoi Diagrams	147	(18)
The Post Office Problem
Definition and Basic Properties	148	(3)
Computing the Voronoi Diagram	151	(9)
Notes and Comments	160	(2)
Exercises	162	(3)
Arrangements and Duality	165	(18)
Supersampling in Ray Tracing
Computing the Discrepancy	167	(2)
Duality	169	(3)
Arrangements of Lines	172	(5)
Levels and Discrepancy	177	(1)
Notes and Comments	178	(2)
Exercises	180	(3)
Delaunay Triangulations	183	(28)
Height Interpolation
Triangulations of Planar Point Sets	185	(3)
The Delaunay Triangulation	188	(3)
Computing the Delaunay Triangulation	191	(6)
The Analysis	197	(3)
A Framework for Randomized Algorithms	200	(6)
Notes and Comments	206	(1)
Exercises	207	(4)
More Geometric Data Structures	211	(24)
Windowing
Interval Trees	212	(6)
Priority Search Trees	218	(5)
Segment Trees	223	(6)
Notes and Comments	229	(1)
Exercises	230	(5)
Convex Hulls	235	(16)
Mixing Things
The Complexity of Convex Hulls in 3-Space	236	(2)
Computing Convex Hulls in 3-Space	238	(4)
The Analysis	242	(3)
Convex Hulls and Half-Space Intersection	245	(2)
Voronoi Diagrams Revisited	247	(1)
Notes and Comments	248	(1)
Exercises	249	(2)
Binary Space Partitions	251	(16)
The Painter's Algorithm
The Definition of BSP Trees	253	(2)
BSP Trees and the Painter's Algorithm	255	(1)
Constructing a BSP Tree	256	(4)
The Size of BSP Trees in 3-Space	260	(3)
Notes and Comments	263	(1)
Exercises	264	(3)
Robot Motion Planning	267	(24)
Getting Where You Want to Be
Work Space and Configuration Space	268	(2)
A Point Robot	270	(5)
Minkowski Sums	275	(6)
Translational Motion Planning	281	(2)
Motion Planning with Rotations	283	(4)
Notes and Comments	287	(2)
Exercises	289	(2)
Quadtrees	291	(16)
Non-Uniform Mesh Generation
Uniform and Non-Uniform Meshes	292	(1)
Quadtrees for Point Sets	293	(7)
From Quadtrees to Meshes	300	(2)
Notes and Comments	302	(2)
Exercises	304	(3)
Visibility Graphs	307	(12)
Finding the Shortest Route
Shortest Paths for a Point Robot	308	(2)
Computing the Visibility Graph	310	(4)
Shortest Paths for a Translating Polygonal Robot	314	(1)
Notes and Comments	315	(1)
Exercises	316	(3)
Simplex Range Searching	319	(22)
Windowing Revisited
Partition Trees	320	(7)
Multi-Level Partition Trees	327	(3)
Cutting Trees	330	(6)
Notes and Comments	336	(1)
Exercises	337	(4)
Bibliography	341	(18)
Index	359