Search This Blog

Monday, November 21, 2011

Computational Geometry by M. de Berg et al (2nd edition) PPT Slides

Introduction and Objective
Introduction to data structures, algorithms, and analysis techniques for computational problems that involve geometry. Line segment intersection. Polygon triangulation and visibility problems. Linear programming. Range queries. Point location. Arrangements and duality. Voronoi diagrams and Delaunay triangulations. Convex hulls. Other selected topics. Programming assignments..
M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf. Computational Geometry (2nd edition). Springer-Verlag, 2000. ISBN: 3-540-65620-0.
The book is accompanied by a website which provides additional material such as pointers to software and research papers. For general background on algorithms, you can consult the following.
J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley, 2005; ISBN 0-321- 29535-8.

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Second Edition MIT Press, 2001; ISBN 0-262-03293-7
Slides download here.

Date Topic
Jan 12 Geometric Basics
Convex Hulls
Jan 14 Line Segment Intersection
Jan 19 Doubly-Connected Edge List
Overlay of Two Subdivisions
Jan 21 The Art Gallery Problem
(Graphs, BFS, DFS )
Jan 26 Triangulation
Jan 28 Half-Plane Intersection
Mar 23 Duality
Mar 25 Arrangement of Lines

No comments:

Post a Comment

Popular Courses

Resources Higher Education Blogs - BlogCatalog Blog Directory Resources Blogs