.

0 (hodnocen0 x )

(4) Půjčeno:4x 

BK

2nd ed.

Cambridge : Cambridge University, 1988

xiii,376 s. : il.

ISBN 0-521-64976-5 (brož.)

Obsahuje nákresy, předmluvu, rejstřík

Bibliografie: s. 351-360

C (jazyk) - geometrie - počítače - využívávní - učebnice

Geometrie - C (jazyk) - počítače - využívávní - učebnice

000014321

Contents // Preface page x // 1. Polygon Triangulation 1 // 1.1 Art Gallery Theorems 1 // 1.2 Triangulation: Theory 11 // 1.3 Area of Polygon 16 // 1.4 Implementation Issues 24 // 1.5 Segment Intersection 27 // 1.6 Triangulation: Implementation 32 // 2. Polygon Partitioning 44 // 2.1 Monotone Partitioning 44 // 2.2 Trapezoidalization 47 // 2.3 Partition into Monotone Mountains 51 // 2.4 Linear-Tmiv Triangulation 56 // 2.5 Convex Partiti ring 58 // 3. Convex Hulls in Two Dimensions 63 // 3.1 Definitions of Convexity and Convex Hulls 64 // 3.2 Naive Algorithms for Extreme Points 66 // 3.3 Gift Wrapping 68 // 3.4 QuickHull 69 // 3.5 Graham’s Algorithm 72 // 3.6 Lower Bound 87 // 3.7 Incremental Algorithm 88 // 3.8 Divide and Conquer 91 // 3.9 Additional Exercises 96 // 4. Convex Hulls in Three Dimensions 101 // 4.1 Polyhedra 101 // 4.2 Hull Algorithms 109 // 4.3 Implementation of Incremental Algorithm 117 // 4.4 Polyhedral Boundary Representations 146 // 4.5 Randomized Incremental Algorithm 149 // 4.6 Higher Dimensions 150 // 4.7 Additional Exercises 153 // viii // Contents // 5. Voronoi Diagrams 155 // 5.1 Applications: Preview 155 // 5.2 Definitions and Basic Properties 157 // 5.3 Delaunay Triangulations 161 // 5.4 Algorithms 165 // 5.5 Applications in Detail 169 // 5.6 Medial Axis 179 // 5.7 Connection to Convex Hulls 182 // 5.8 Connection to Arrangements 191 // 6. Arrangements 193 // 6.1 Introduction 193 // 6.2 Combinatorics of Arrangements 194 // 6.3 Incremental Algorithm 199

// 6.4 Three and Higher Dimensions 201 // 6.5 Duality 201 // 6.6 Higher-Order Voronoi Diagrams 205 // 6.7 Applications 209 // 6.8 Additional Exercises 218 // 7. Search and Intersection 220 // 7.1 Introduction 220 // 7.2 Segment-Segment Intersection 220 // 7.3 Segment-Triangle Intersection 226 // 7.4 Point in Polygon 239 // 7.5 Point in Polyhedron 245 // 7.6 Intersection of Convex Polygons 252 // 7.7 Intersection of Segments 263 // 7.8 Intersection of Nonconvex Polygons 266 // 7.9 Extreme Point of Convex Polygon 269 // 7.10 Extremal Polytope Queries 272 // 7.11 Planar Point Location 285 // 8. Motion Planning 294 // 8.1 Introduction 294 // 8.2 Shortest Paths 295 // 8.3 Moving a Disk 300 // 8.4 Translating a Convex Polygon 302 // 8.5 Moving a Ladder 313 // 8.6 Robot Arm Motion 322 // 8.7 Separability 339 // 9. Sources 347 // 9.1 Bibliographies and FAQs 347 // 9.2 Textbooks 347 // 9.3 Book Collections 348 // Contents // ix // 9.4 Monographs 349 // 9.5 Journals 349 // 9.6 Conference Proceedings 350 // 9.7 Software 350 // Bibliography 351 // Index 361