中文名: 計算幾何--算法與應用
原名: Computational Geometry:Algorithms and Applications
作者: (荷)Mark de Berg, Marc van Kreveld等
資源格式: PDF
版本: 第3版　清晰版
出版社: Springer Berlin Heidelberg
書號: 3642096816
發行時間: 2009年
地區: 美國
語言: 英文
簡介:

內容簡介：
計算幾何是計算機理論科學的一個重要分支.自20世紀70年代末從算法設計與分析中獨立出來起，不到30年，該學科已經有了巨大的發展，不僅產生了一系列重要的理論成果，也在眾多實際領域中得到了廣泛的應用.
本書的前4章對幾何算法進行了討論，包括幾何求交、三角剖分、線性規劃等，其中涉及的隨機算法也是本書的一個鮮明特點.第5章至第10章介紹了多種幾何結構，包括幾何查找、kd樹、區域樹、梯形圖、Voronoi圖、排列、Delaunay三角剖分、區間樹、優先查找樹以及線段樹等.第11章至第16章結合實際問題，繼續討論了若干幾何算法及其數據結構，包括高維凸包、空間二分及BSP樹、運動規劃、網格生成及四叉樹、最短路徑查找及可見性圖、單純性區域查找及劃分樹和切分樹等，這些也是對前十章內容的進一步深化.
本書不僅內容全面，而且緊扣實際應用，重點突出，既有深入的講解，同時每章都設有“注釋及評論”和“習題”，為讀者更深入的理解提供了可能.
Errata, Pseudocode: http://www.cs.uu.nl/geobook/
內容截圖：

目錄:
Table of Contents
1 Computational Geometry --- Introduction
1.1 An Example: Convex Hulls
1.2 Degeneracies and Robustness
1.3 Application Domains
1.4 Notes and Comments
1.5 Exercises
2 Line Segment Intersection --- Thematic Map Overlay
2.1 Line Segment Intersection
2.2 The Doubly-Connected Edge List
2.3 Computing the Overlay of Two Subdivisions
2.4 Boolean Operations
2.5 Notes and Comments
2.6 Exercises
3 Polygon Triangulation --- Guarding an Art Gallery
3.1 Guarding and Triangulations
3.2 Partitioning a Polygon into Monotone Pieces
3.3 Triangulating a Monotone Polygon
3.4 Notes and Comments
3.5 Exercises
4 Linear Programming --- Manufacturing with Molds
4.1 The Geometry of Casting
4.2 Half-Plane Intersection
4.3 Incremental Linear Programming
4.4 Randomized Linear Programming
4.5 Unbounded Linear Programs
4.6* Linear Programming in Higher Dimensions
4.7* Smallest Enclosing Discs
4.8 Notes and Comments
4.9 Exercises
5 Orthogonal Range Searching --- Querying a Database
5.1 1-Dimensional Range Searching
5.2 Kd-Trees
5.3 Range Trees
5.4 Higher-Dimensional Range Trees
5.5 General Sets of Points
5.6* Fractional Cascading
5.7 Notes and Comments
5.8 Exercises
6 Point Location --- Knowing Where You Are
6.1 Point Location and Trapezoidal Maps
6.2 A Randomized Incremental Algorithm
6.3 Dealing with Degenerate Cases
6.4* A Tail Estimate
6.5 Notes and Comments
6.6 Exercises
7 Voronoi Diagrams --- The Post Office Problem
7.1 Definition and Basic Properties
7.2 Computing the Voronoi Diagram
7.3 Voronoi Diagrams of Line Segments
7.4 Farthest-Point Voronoi Diagrams
7.5 Notes and Comments
7.6 Exercises
8 Arrangements and Duality --- Supersampling in Ray Tracing
8.1 Computing the Discrepancy
8.2 Duality
8.3 Arrangements of Lines
8.4 Levels and Discrepancy
8.5 Notes and Comments
8.6 Exercises
9 Delaunay Triangulations --- Height Interpolation
9.1 Triangulations of Planar Point Sets
9.2 The Delaunay Triangulation
9.3 Computing the Delaunay Triangulation
9.4 The Analysis
9.5* A Framework for Randomized Algorithms
9.6 Notes and Comments
9.7 Exercises
10 More Geometric Data Structures --- Windowing
10.1 Interval Trees
10.2 Priority Search Trees
10.3 Segment Trees
10.4 Notes and Comments
10.5 Exercises
11 Convex Hulls --- Mixing Things
11.1 The Complexity of Convex Hulls in 3-Space
11.2 Computing Convex Hulls in 3-Space
11.3* The Analysis
11.4* Convex Hulls and Half-Space Intersection
11.5* Voronoi Diagrams Revisited
11.6 Notes and Comments
11.7 Exercises
12 Binary Space Partitions --- The Painter's Algorithm
12.1 The Definition of BSP Trees
12.2 BSP Trees and the Painter's Algorithm
12.3 Constructing a BSP Tree
12.4* The Size of BSP Trees in 3-Space
12.5 BSP Trees for Low-Density Scenes
12.6 Notes and Comments
12.7 Exercises
13 Robot Motion Planning --- Getting Where You Want To Be
13.1 Work Space and Configuration Space
13.2 A Point Robot
13.3 Minkowski Sums
13.4 Translational Motion Planning
13.5* Motion Planning with Rotations
13.6 Notes and Comments
13.7 Exercises
14 Quad Trees --- Non-Uniform Mesh Generation
14.1 Uniform and Non-Uniform Meshes
14.2 Quad Trees for Point Sets
14.3 From Quad Trees to Meshes
14.4 Notes and Comments
14.5 Exercises
15 Visibility Graphs --- Finding the Shortest Route
15.1 Shortest Paths for a Point Robot
15.2 Computing the Visibility Graph
15.3 Shortest Paths for a Translating Polygonal Robot
15.4 Notes and Comments
15.5 Exercises
16 Simplex Range Searching --- Windowing Revisited
16.1 Partition Trees
16.2 Multi-Level Partition Trees
16.3 Cutting Trees
16.4 Notes and Comments
16.5 Exercises