Joseph ORourke 美國馬薩諸塞州史密斯學院計算機科學系主任、數(shù)學系教授。自1980年從賓夕法尼亞大學獲得計算機科學專業(yè)博士學位以后,他就一直致力于該領(lǐng)域的教學與研究。研究方向主要為計算幾何,除了本書外,他還著有Art Gallery Theorems and Algorithms一書,并與J.E.Goodman一起編寫了1000頁的Handbook of Discrete and Computational Geonetry,此外,還發(fā)表了70多篇關(guān)于計算機幾何方面的論文以及為“計算機幾何專欄”寫過30多篇文章,由于對該領(lǐng)域的卓越貢獻,2001年他兒美國國家基金會來出教師獎。
圖書目錄
Preface 1. Polygon triangulation; 1.1 Art Gallery Theorems 1.2 Triangulation:Theory 1.3 Area of Polygon 1.4 Implementation Issues 1.5 Segment Intersection 1.6 Triangulation:Implementation 2. Polygon partitioning; 2.1 Monotone Partitioning 2.2 Trapezoidalization 2.3 Partition into Monotone Mountains 2.4 Linear-Time Triangulation 2.5 Convex partitioning 3. Convex hulls in two dimensions; 3.1 Definitons of Convexity and Convex Hulls 3.2 Naive Algorithms for Extreme Points 3.3 Gift Wrapping 3.4 QuickHull 3.5 Graham's Algorithm 3.6 Lower Bound 3.7 Incremental Algorithm 3.8 Divide and Conquer 3.9 Additional Exercises 4. Convex hulls in three dimensions; 4.1 Polyhedra 4.2 Hull Algorithms 4.3 Implementation of Incremental Algorithm 4.4 Polyhedral Boundary Representations 4.5 Randomized Incremental Algorithm 4.6 Higher Dimensions 4.7 Addditional Exercises 5. Voronoi diagrams; 5.1 Applications:Preview 5.2 Defintions and Basic properties 5.3 Delaunay Triangulations 5.4 Algorithms 5.5 Applications in Detail 5.6 Medial Axis 5.7 Connection to Conves Hulls 5.8 Connection to Arrangements 6. Arrangements; 6.1 Introduction 6.2 Combilnatorics of Arrangements 6.3 Incremental Algorithm 6.4 Three and Higher Dimensions 6.5 Duality 6.6 Higher_Order Voronoi Diagrams 6.7 Applications 6.8 Sdditional Exercises 7. Search and intersection; …… 8. Motion planning; 9. Sources. Bibliography Index