Computational Geometry: Algorithms and Applications

Springer Science & Business Media, 2000 - 367 Seiten
This well-accepted introduction to computational geometry is a textbook for high-level undergraduate and low-level graduate courses. The focus is on algorithms and hence the book is well suited for students in computer science and engineering. Motivation is provided from the application areas: all solutions and techniques from computational geometry are related to particular applications in robotics, graphics, CAD/CAM, and geographic information systems. For students this motivation will be especially welcome. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement. All the basic techniques and topics from computational geometry, as well as several more advanced topics, are covered. The book is largely self-contained and can be used for self-study by anyone with a basic background in algorithms. In the second edition, besides revisions to the first edition, a number of new exercises have been added.

Inhalt

 Computational Geometry Introduction 1 Convex Hulls 2 12 Degeneracies and Robustness 8 13 Application Domains 10 14 Notes and Comments 13 15 Exercises 15 Line Segment Intersection Thematic Map Overlay 19 21 Line Segment Intersection 20
 91 Triangulations of Planar Point Sets 185 92 The Delaunay Triangulation 188 93 Computing the Delaunay Triangulation 191 94 The Analysis 197 95 A Framework for Randomized Algorithms 200 96 Notes and Comments 206 97 Exercises 207 More Geometric Data Structures Windowing 211

 22 The DoublyConnected Edge List 29 23 Computing the Overlay of Two Subdivisions 33 24 Boolean Operations 39 25 Notes and Comments 40 26 Exercises 42 Polygon Triangulation Guarding an Art Gallery 45 31 Guarding and Triangulations 46 32 Partitioning a Polygon into Monotone Pieces 49 33 Triangulating a Monotone Polygon 55 34 Notes and Comments 59 35 Exercises 60 Linear Programming Manufacturing with Molds 63 41 The Geometry of Casting 64 42 HalfPlane Intersection 66 43 Incremental Linear Programming 71 44 Randomized Linear Programming 77 45 Unbounded Linear Programs 80 46 Linear Programming in Higher Dimensions 82 47 Smallest Enclosing Discs 86 48 Notes and Comments 90 49 Exercises 91 Orthogonal Range Searching Querying a Database 95 51 1Dimensional Range Searching 96 52 KdTrees 99 53 Range Trees 105 54 HigherDimensional Range Trees 109 55 General Sets of Points 111 56 Fractional Cascading 112 57 Notes and Comments 115 58 Exercises Section 117 Point Location Knowing Where You Are 121 61 Point Location and Trapezoidal Maps 122 62 A Randomized Incremental Algorithm 128 63 Dealing with Degenerate Cases 137 64 A Tail Estimate 140 65 Notes and Comments 143 66 Exercises 144 Voronoi Diagrams The Post Office Problem 147 71 Definition and Basic Properties 148 72 Computing the Voronoi Diagram 151 73 Notes and Comments 160 74 Exercises 162 Arrangements and Duality Supersampling in Ray Tracing 165 81 Computing the Discrepancy 167 82 Duality 169 83 Arrangements of Lines 172 84 Levels and Discrepancy 177 85 Notes and Comments 178 86 Exercises 180 Delaunay Triangulations Height Interpolation 183
 101 Interval Trees 212 102 Priority Search Trees 218 103 Segment Trees 223 104 Notes and Comments 229 105 Exercises 230 Convex Hulls Mixing Things 235 111 The Complexity of Convex Hulls in 3Space 236 112 Computing Convex Hulls in 3Space 238 113 The Analysis 242 114 Convex Hulls and HalfSpace Intersection 245 115 Voronoi Diagrams Revisited 247 116 Notes and Comments 248 117 Exercises 249 Binary Space Partitions The Painters Algorithm 251 121 The Definition of BSP Trees 253 122 BSP Trees and the Painters Algorithm 255 123 Constructing a BSP Tree 256 124 The Size of BSP Trees in 3Space 260 125 Notes and Comments 263 126 Exercises 264 Robot Motion Planning Getting Where You Want to Be 267 131 Work Space and Configuration Space 268 132 A Point Robot 270 133 Minkowski Sums 275 134 Translational Motion Planning 281 135 Motion Planning with Rotations 283 136 Notes and Comments 287 137 Exercises 289 Quadtrees NonUniform Mesh Generation 291 141 Uniform and NonUniform Meshes 292 142 Quadtrees for Point Sets 293 143 From Quadtrees to Meshes 300 144 Notes and Comments 302 145 Exercises 304 Visibility Graphs Finding the Shortest Route 307 151 Shortest Paths for a Point Robot 308 152 Computing the Visibility Graph 310 153 Shortest Paths for a Translating Polygonal Robot 314 154 Notes and Comments 315 155 Exercises 316 Simplex Range Searching Windowing Revisited 319 161 Partition Trees 320 162 MultiLevel Partition Trees 327 163 Cutting Trees 330 164 Notes and Comments 336 165 Exercises 337 Bibliography 341 Index 359 Urheberrecht

Beliebte Passagen

Seite 345 - Y.-J. Chiang, FP Preparata, and R. Tamassia. A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps.
Seite 343 - J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Discrete Comput.
Seite iv - Department of Computer Science, Utrecht University PO Box 80.089, 3508 TB Utrecht, The Netherlands Abstract...

Verweise auf dieses Buch

 Geometric Methods and Applications: For Computer Science and EngineeringJean H. GallierEingeschränkte Leseprobe - 2001
 Full-Chip Nanometer Routing TechniquesKeine Leseprobe verfügbar - 2007
Alle Ergebnisse von Google Books &raquo;