中文名: 计算几何--算法与应用原名: 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树、运动规划
、网格生成及四叉树 、最短路径查找及可见性图、单纯性区域查找及划分树和切分树等，这些也是对前十章内容的进一步深化.本书不仅内容全面 ，而且紧扣实际应用，重点突出，既有深入的讲解，同时每章都设有“注释及评论”和“习题”，为读者更深入的理解提供了可能. 目录: Table of Contents1 Computational Geometry --- Introduction1.1 An Example: Convex Hulls1.2 Degeneracies and Robustness1.3 Application Domains1.4 Notes and Comments1.5 Exercises2 Line Segment Intersection --- Thematic Map Overlay2.1 Line Segment Intersection2.2 The Doubly-Connected Edge List2.3 Computing the Overlay of Two Subdivisions2.4 Boolean Operations2.5 Notes and Comments2.6 Exercises3 Polygon Triangulation --- Guarding an Art Gallery3.1 Guarding and Triangulations3.2 Partitioning a Polygon into Monotone Pieces3.3 Triangulating a Monotone Polygon3.4 Notes and Comments3.5 Exercises4 Linear Programming --- Manufacturing with Molds4.1 The Geometry of Casting4.2 Half-Plane Intersection4.3 Incremental Linear Programming4.4 Randomized Linear Programming4.5 Unbounded Linear Programs4.6* Linear Programming in Higher Dimensions4.7* Smallest Enclosing Discs4.8 Notes and Comments4.9 Exercises5 Orthogonal Range Searching --- Querying a Database5.1 1-Dimensional Range Searching5.2 Kd-Trees5.3 Range Trees5.4 Higher-Dimensional Range Trees5.5 General Sets of Points5.6* Fractional Cascading5.7 Notes and Comments5.8 Exercises6 Point Location --- Knowing Where You Are6.1 Point Location and Trapezoidal Maps6.2 A Randomized Incremental Algorithm6.3 Dealing with Degenerate Cases6.4* A Tail Estimate6.5 Notes and Comments6.6 Exercises7 Voronoi Diagrams --- The Post Office Problem7.1 Definition and Basic Properties7.2 Computing the Voronoi Diagram7.3 Voronoi Diagrams of Line Segments7.4 Farthest-Point Voronoi Diagrams7.5 Notes and Comments7.6 Exercises8 Arrangements and Duality --- Supersampling in Ray Tracing8.1 Computing the Discrepancy8.2 Duality8.3 Arrangements of Lines8.4 Levels and Discrepancy8.5 Notes and Comments8.6 Exercises9 Delaunay Triangulations --- Height Interpolation9.1 Triangulations of Planar Point Sets9.2 The Delaunay Triangulation9.3 Computing the Delaunay Triangulation9.4 The Analysis9.5* A Framework for Randomized Algorithms9.6 Notes and Comments9.7 Exercises10 More Geometric Data Structures --- Windowing10.1 Interval Trees10.2 Priority Search Trees10.3 Segment Trees10.4 Notes and Comments10.5 Exercises11 Convex Hulls --- Mixing Things11.1 The Complexity of Convex Hulls in 3-Space11.2 Computing Convex Hulls in 3-Space11.3* The Analysis11.4* Convex Hulls and Half-Space Intersection11.5* Voronoi Diagrams Revisited11.6 Notes and Comments11.7 Exercises12 Binary Space Partitions --- The Painter's Algorithm12.1 The Definition of BSP Trees12.2 BSP Trees and the Painter's Algorithm12.3 Constructing a BSP Tree12.4* The Size of BSP Trees in 3-Space12.5 BSP Trees for Low-Density Scenes12.6 Notes and Comments12.7 Exercises13 Robot Motion Planning --- Getting Where You Want To Be13.1 Work Space and Configuration Space13.2 A Point Robot13.3 Minkowski Sums13.4 Translational Motion Planning13.5* Motion Planning with Rotations13.6 Notes and Comments13.7 Exercises14 Quad Trees --- Non-Uniform Mesh Generation14.1 Uniform and Non-Uniform Meshes14.2 Quad Trees for Point Sets14.3 From Quad Trees to Meshes14.4 Notes and Comments14.5 Exercises15 Visibility Graphs --- Finding the Shortest Route15.1 Shortest Paths for a Point Robot15.2 Computing the Visibility Graph15.3 Shortest Paths for a Translating Polygonal Robot15.4 Notes and Comments15.5 Exercises16 Simplex Range Searching --- Windowing Revisited16.1 Partition Trees16.2 Multi-Level Partition Trees16.3 Cutting Trees16.4 Notes and Comments16.5 Exercises