《计算几何(第3版)》为世界著名计算机教材精选之一。全书共分十六章，主要内容包括线段求交：专题图叠合，正交区域查找：数据库查询，点定位：找到自己的位置，Voronoi图：邮局问题，更多几何数据结构：截窗，空间二分：画家算法，可见性图：求最短路径等。本书不仅内容全面，而且紧扣实际应用，重点突出，既有深入的讲解，同时每章都设有“注释及评论”和“习题”，方便读者更深入的理解，被世界众多大学作为教材。本书由荷兰伯格著。

1 ComputationaI Geometry Introduction

1.1 AnExample: Convex Hulls

1.2 Degeneracies and Robustness

1.3 Application Domains

1.4 Notes and Comments

1.5 Exercises

2 Line Segment lntersection Thematic Map Overlay

2.1 Line Segment lntersection

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 GaHery

3.1 Guarding and Triangulations

3.2 Partitioning a Polygon in to Monotone Pieces

3.3 Triangulating a Monotone Polygon

3.4 Notes and Comments

3.5 Exercises

4 Linear Programming

Manufacturing witb Molds

4.1 The Geometry of Casting

4.2 Half-Planelntersection

4.3 IncrementaILinear Programnung

4.4 Randomized Linear Programming

4.5 Unbounded Linear Programs

4.6 *Linear Programmingin Higher Dimensions

4.7 *Smallest Enclosing Discs

4.8 Notes and Comments

4.9 Exercises

5 OrthogonaI Range Searching Querying a Database

5.1 l-Dimensional Range Searching

5.2 Kd-Trees

5.3 RangeTrees

5.4 Higher-DimensionaIRangeTrees

5.5 General Sets ofPoints

5.6 FractionaI Cascading .

5.7 Notes and Comments

5.8 Exercises

6 PointLocation Knowing Where You Are

6.1 PointLocation and TrapczoidaIMaps

6.2 ARandomizedIncrementaI Algorithm

6.3 Dealing with Degenerate Cases

6.4 *ATaiI Estimate

6.5 Notes and Comments

6.6 Exercises

7 Voronoi Diagrams

The Post Orffice Problem

7.1 Definition and Basic Ptoperties

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

……

9 Delaunay Triangulations Hejght Interpolation

10 More Geometric Data Structures Windowing

11 Convex Hulls Mixing Things

12 Binary Space Partitions The Painter's Algorithm

13 Robot Motion Plaruung Getting Where You Want to Be

14 Quadtrees Non-Uruform Mesh Generation

15 Visibility Graphs Finding the Shortest Route

16 Simplex Range Searching Windowing Revisited

Bibliography

Index