Lecture plan ECS-071 COMPUTATIONAL GEOMETRY |
||
Unit |
Topic |
Lecture |
Unit I |
Introduction to Computational Geometry |
Lecture 1 |
Applications of Computational Geometry |
Lecture 2 |
|
Convex hulls: construction in 2d and 3d, |
Lecture 3 |
|
lower bounds; |
Lecture 4 |
|
Triangulations: Introduction |
Lecture 5 |
|
Polygon triangulations, |
Lecture 6 |
|
Triangulations: representations, |
Lecture 7 |
|
Point-set triangulations |
Lecture 8 |
|
Planar graphs |
Lecture 9 |
|
Unit II |
Voronoi diagrams: construction |
Lecture 10 |
Voronoi diagrams: applications, variants; |
Lecture 11 |
|
Delayney triangulations: divide-and conquer, |
Lecture 12 |
|
flip and incremental algorithms, |
Lecture 13 |
|
flip and incremental algorithms: Case Studies and examples, |
Lecture 14 |
|
Duality of Voronoi diagrams: Introduction |
Lecture 15 |
|
Duality of Voronoi diagrams: case studies |
Lecture 16 |
|
Min-max angle properties |
Lecture 17 |
|
Unit III |
Geometric searching: point-location, |
Lecture 18 |
fractional cascading, |
Lecture 19 |
|
linear programming with prune and search, |
Lecture 20 |
|
finger trees, concatenable queues, |
Lecture 21 |
|
segment trees, interval trees; |
Lecture 22 |
|
Visibility: algorithms for weak and strong visibility, |
Lecture 23 |
|
visibility with reflections, |
Lecture 24 |
|
art-gallery problems |
Lecture 25 |
|
Unit IV |
Arrangements of lines: arrangements of hyper planes, |
Lecture 26 |
zone theorems, |
Lecture 27 |
|
many-faces complexity and algorithms; |
Lecture 28 |
|
zone theorems: case studies |
Lecture 29 |
|
Combinatorial geometry: Ham-sandwich cuts. |
Lecture 30 |
|
Unit V |
Sweep techniques: plane sweep for segment intersections, |
Lecture 31 |
Fortune's sweep for Voronoi diagrams, |
Lecture 32 |
|
topological sweep for line arrangements; |
Lecture 33 |
|
Randomization in computational geometry: algorithms, techniques for counting; |
Lecture 34 |
|
Randomization: Examples, |
Lecture 34 |
|
Robust geometric computing, |
Lecture 35 |
|
Robust geometric computing: Examples, |
Lecture 36 |
|
More Applications and case studies of computational geometry; |
Lecture 37 |
|
References: 1. Computational Geometry: An Introduction by Franco P. Preparata and Michael Ian Shamos; Springer Verlag 4. Joseph O'Rourke, Computational Geometry in C, Cambridge University Press |