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..Textbook
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 http://www.cs.uu.nl/geobook/ 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.Slides download here.
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
| 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