计算几何-第3版_PDF下载[82MB-百度云]（荷）伯格著

节选

[

《计算几何(第3版)》由世界图书出版公司北京公司出版。

]

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 line segment intersection thematic map overlay 2.1 line segment intersection 2.2 the doubly-connected edge list 2.3 computing the overlay of twosubdivisions 2.4 boolean operations 2.5 notes and comments 2.6 exercises polygon triangulation guarding an art gallery 3.1 guarding and triangulations 3.2 partitioning a polygon into monotonepieces 3.3 triangulating a monotone polygon 3.4 notes and comments 3.5 exercises 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 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 exercises6 point location knowing where you are 6.1 point location and trapezoidalmaps 6.2 a randomized incrementalalgorithm 6.3 dealing with degenerate cases 6.4* a tail estimate 6.5 notes and comments 6.6 exercises7 voronoi diagrams the post office problem 7.1 definition and basic properties 7.2 computing the voronoi diagram 7.3 voronoi diagrams of linesegments 7.4 farthest-point voronoi diagrams 7.5 notes and comments 7.6 exercises 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 delaunay triangulations height interpolation 9.1 triangulations of planar pointsets 9.2 the delaunay triangulation 9.3 computing the delaunaytriangulation 9.4 the analysis 9.5* a framework for randomized algorithms 9.6 notes and comments 9.7 exercises10 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 exercises11 convex hulls mixing things 11.1 the complexity of convex hulls in3-space 11.2 computing convex hulls in 3-space 11.3″ the analysis 11.4′ convex hulls and half-spaceintersection 11.5′ voronoi diagrams revisited 11.6 notes and comments 11.7 exercises12 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 exercises13 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 exercises14 quadtrees non-uniform mesh generation 14.1 uniform and non-uniform meshes 14.2 quadtrees for point sets 14.3 from quadtrees to meshes 14.4 notes and comments 14.5 exercises15 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 polygonalrobot 15.4 notes and comments 15.5 exercises16 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 exercisesbibliographyindex