计算几何--算法与应用（第2版）（中文版）.pdf

中文名: 计算几何--算法与应用 原名: 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 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 Estima