Computational Geometry: Algorithms and Applications

Cover
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

Andere Ausgaben - Alle anzeigen

Computational Geometry: Algorithms and Applications
Mark de Berg,Marc van Krefeld,Mark Overmars,Otfried Cheong
Eingeschränkte Leseprobe - 2013
Computational Geometry: Algorithms and Applications
Mark de Berg,Marc Van Kreveld,Mark Overmars,Otfried Schwarzkopf
Eingeschränkte Leseprobe - 2000
Computational Geometry
Mark de Berg,Marc Van Krefeld,Mark Overmars
Keine Leseprobe verfügbar - 2014

Häufige Begriffe und Wortgruppen

2-dimensional algorithm answer arrangement assume bound boundary called canonical subsets Chapter circle complexity compute configuration connected consider construct contains convex hull corresponding created data structure defined Delaunay denote described determine direction doubly-connected edge list edge endpoint event example exists expected face facets Figure geometric give given graph half-edge half-planes Hence input insertion inside interior intersection intervals leaf Lemma lies line segments linear program look means mesh Minkowski sum motion node Notes O(nlogn objects obstacles partition path planar plane planning points polygon position possible problem Proof prove quadtree query random range region reported result robot root running set of points side simple smallest solution solve space split square storage stored subdivision subtree sweep line takes Theorem trapezoids tree triangulation upper vertex vertices visible Voronoi diagram y-coordinate

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.
Wird in 20 Büchern von 1931 bis 2004 erwähnt
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.
Wird in 26 Büchern von 1991 bis 2005 erwähnt
Seite iv - Department of Computer Science, Utrecht University PO Box 80.089, 3508 TB Utrecht, The Netherlands Abstract...
Wird in 68 Büchern von 1967 bis 2004 erwähnt

Verweise auf dieses Buch

Bibliografische Informationen

QR code for Computational Geometry
TitelComputational Geometry: Algorithms and Applications
Autor/inMark de Berg
Ausgabeillustriert
VerlagSpringer Science & Business Media, 2000
ISBN3540656200, 9783540656203
Länge367 Seiten
  
Zitat exportierenBiBTeX EndNote RefMan