Computational Geometry: Algorithms and ApplicationsThis 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. |
Contents
I | 1 |
II | 19 |
III | 25 |
V | 41 |
VI | 63 |
VII | 85 |
VIII | 111 |
X | 129 |
XII | 165 |
XIV | 169 |
XVI | 177 |
XVII | 193 |
XVIII | 201 |
XIX | 217 |
XXI | 229 |
XI | 145 |
Other editions - View all
Common terms and phrases
3-dimensional 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 disjoint doubly-connected edge list dual plane event point face facets Figure geometric graph half-edge half-plane Hence horizontal Input insert interior intersection point kd-tree leaf Lemma lies LINE SEGMENT INTERSECTION linear program Minkowski sum motion planning number of edges number of reported number of vertices O(n² O(nlogn obstacles P₁ partition tree planar plane sweep point location point q pointers primal plane priority search tree problem Proof prove pseudodiscs Pstart quadtree query algorithm query point range queries range searching range tree recursive region robot search path search structure Section segment tree set of points shortest path simple polygon simplicial partition split storage stored subdivision subtree sweep line Theorem total number trapezoidal map triangles vertex vertical line Voronoi diagram y-coordinate
Popular passages
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 |
Full-Chip Nanometer Routing Techniques Tsung-Yi Ho,Yao-Wen Chang,Sao-Jie Chen No preview available - 2007 |