.

0 (hodnocen0 x )

(2) Půjčeno:2x 

BK

Princeton : Princeton University Press, c2011

xi, 255 s. : il. ; 27 cm

ISBN 978-0-691-14553-2 (váz.)

Obsahuje bibliografie a rejstřík

000251893

Contents // Preface ix // 1 POLYGONS // 1.1 Diagonals and Triangulations 1 // 1.2 Basic Combinatorics 7 // 1.3 The Art Gallery Theorem 13 // 1.4 Scissors Congruence in 2D 20 // 1.5 Scissors Congruence in 3D 26 // 2 CONVEX HULLS // 2.1 Convexity 33 // 2.2 The Incremental Algorithm 36 // 2.3 Analysis of Algorithms 39 // 2.4 Gift Wrapping and Graham Scan 42 // 2.5 Lower Bound 46 // 2.6 Divide-and-Conquer 48 // 2.7 Convex Hull in 3D 51 // 3 TRIANGULATIONS // 3.1 Basic Constructions 59 // 3.2 The Flip Graph 66 // 3.3 The Associahedron 73 // 3.4 Delaunay Triangulations 79 // 3.5 Special Triangulations 87 // 4 VORONOI DIAGRAMS // 4.1 Voronoi Geometry 98 // 4.2 Algorithms to Construct the Diagram 104 // 4.3 Duality and the Delaunay Triangulation 107 // 4.4 Convex Hull Revisited 113 // 5 CURVES // 5.1 Medial Axis 118 // 5.2 Straight Skeleton 125 // 5.3 Minkowski Sums 128 // 5.4 Convolution of Curves 132 // viii CONTENTS // 5.5 Curve Shortening 138 // 5.6 The Heat Equation 144 // 5.7 Curve Reconstruction 148 // 6 POLYHEDRA // 6.1 Platonic Solids 156 // 6.2 Euler’s Polyhedral Formula 162 // 6.3 The Gauss-Bonnet Theorem 170 // 6.4 Cauchy Rigidity 177 // 6.5 Shortest Paths 188 // 6.6 Geodesics 200 // 7 CONFIGURATION SPACES // 7.1 Motion Planning 206 // 7.2 Polygonal Chains 215 // 7.3 Rulers and Locked Chains 221 // 7.4 Polygon Spaces 229 // 7.5 Particle Collisions 237 // Appendix: Computational Complexity 245 // Permissions 249 // Index 251