Computational Geometry: Algorithms and ApplicationsThis wellaccepted introduction to computational geometry is a textbook for highlevel undergraduate and lowlevel 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 selfcontained and can be used for selfstudy 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 stars 
 
3 stars 
 
2 stars 
 
1 star 

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 
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 
341  
359  
Other editions  View all
Common terms and phrases
2dimensional associated structure beach line bound boundary BSP tree canonical subsets Chapter complexity computational geometry configuration space construct contains convex hull convex polygon corresponding data structure defined Delaunay triangulation denote diagonal disc doublyconnected edge list dual endpoint event point face facets Figure geometric halfedge halfplanes Hence input interior intersection point interval tree kdtree leaf Lemma lies LINE SEGMENT INTERSECTION line segments linear program mesh Minkowski sum motion planning Notes and Comments number of reported O(logn O(n\ogn objects obstacles partition tree pixel planar plane sweep point location point q pointers problem Proof prove quadtree query algorithm query point query range range queries range searching range tree recursive region robot search path search structure Section SEGMENT INTERSECTION segment tree set of points shortest path simple polygon square subdivision subtree sweep line Theorem total number trapezoidal map triangles vcoordinate vertex visibility graph Vor(P Voronoi diagram
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:353373, 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 online algorithms in computational geometry. Discrete Comput.
Page 354  M. Pocchiola and G. Vegter. Topologically sweeping visibility complexes via pseudotriangulations.
Page 353  MH Overmars and J. van Leeuwen. Dynamization of decomposable searching problems yielding good worstcase bounds.
Page 357  New Heuristic Algorithms for Efficient Hierarchical Path Planning", IEEE Trans. On Robotics and Automation, 7(1), 919, 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 Engineering Jean H. Gallier Limited preview  2001 
FullChip Nanometer Routing Techniques TsungYi Ho,YaoWen Chang,SaoJie Chen No preview available  2007 