# Computational Geometry: Algorithms and Applications

Springer Science & Business Media, 2000 - Computers - 367 pages
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.

### What people are saying -Write a review

#### User ratings

5 stars
 4
4 stars
 3
3 stars
 0
2 stars
 0
1 star
 0

User Review - Flag as inappropriate

my books is here

User Review - Flag as inappropriate

a great book of all time.

### Contents

 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

### Popular passages

Page 356 - Halperin, and MH Overmars. The complexity of the free space for a robot moving amidst fat obstacles. Comput. Geom. Theory Appl., 3:353-373, 1993.
Page 345 - Y.-J. Chiang, FP Preparata, and R. Tamassia. A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps.
Page 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.
Page 354 - M. Pocchiola and G. Vegter. Topologically sweeping visibility complexes via pseudo-triangulations.
Page 353 - MH Overmars and J. van Leeuwen. Dynamization of decomposable searching problems yielding good worst-case bounds.
Page 357 - New Heuristic Algorithms for Efficient Hierarchical Path Planning", IEEE Trans. On Robotics and Automation, 7(1), 9-19, 1991.
Page iv - Department of Computer Science, Utrecht University PO Box 80.089, 3508 TB Utrecht, The Netherlands Abstract...

### References to this book

 Geometric Methods and Applications: For Computer Science and EngineeringJean H. GallierLimited preview - 2001
 Full-Chip Nanometer Routing TechniquesNo preview available - 2007
All Book Search results &raquo;