| Course Outline | General Information | Study Material | Lectures (classwise) |
The course consists of 2 double lectures per week.
The basic thrust of the course would be to study discrete and computational geometry.
We will try to stick to the basic course outline as given in this page, but may deviate a bit.
We would assume in this course that you have undergone the Data and File Structures, Design and Analysis of Algorithms and Discrete Structures courses and have some knowledge of elementary discrete probability.
| Class Timings: | Monday 14:15-16:05, Thursday 09:45-11:25 Room No. 709-710, S. N. Bose Bhavan (Library Building) |
| The necessary evil - marks, exam, etc.: | Mid-sem: 25, End-sem: 50, Internal evaluation: 25 |
| Books |
(B1) Computational Geometry: Algorithms and Applications Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars Springer Verlag (B2) Computational Geometry -- An Introduction Franco Preparata and Michael Ian Shamos Springer Verlag (B3) Computational Geometry in C Joseph O'Rourke Cambridge University Press (B4) Computational Geometry: An Introduction Through Randomized Algorithms Ketan Mulmuley Prentice Hall (B5) Geometric Approximation Algorithms Sariel Har-Peled American Mathematical Society (B6) Algorithms in Combinatorial Geometry Herbert Edelsbrunner Springer-Verlag (B7) Algorithmic Geometry J-D. Boissonnat and M. Yvinec Cambridge University Press (B8) Randomized Algorithms Rajeev Motwani and Prabhakar Raghavan Cambridge |
| Web Resources |
(W1) Lecture Notes by David Mount (W2) Video lectures by Prof. Sandeep Sen |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (04-08-2014) |
Introduction, convex hull in 2D -- lower bound, Graham's scan, Jarvis march, output sensitive Chan's algorithm. | - | (B1), (B2), (W1) |
| Lecture 2 (07-08-14) |
Range search -- Kd tree, Range tree | - | (B1), (B2), (W1) |
| Lecture 3 (11-08-14) |
Range search (contd.) -- Fractional Cascading Art Gallery theorem |
- | (B1), (B2), (B3), (W1) |
| Lecture 4 (12-08-14) |
Polygon triangulation: area of a simple polygon, counting the number of triangulations in a convex polygon |
- | (B1), (B2), (B3), (W1) |
| Lecture 5 (14-08-14) |
Plane sweep -- the general paradigm Line segment intersection |
- | (B1), (W1) |
| Lecture 6 (28-08-14) |
Doubly Connected Edge List (DCEL) Triangulation of a monotone polygon |
- | (B1), (W1) |
| Lecture 7 (29-08-14) |
Voronoi diagram | - | (B1), (W1) |
| Lecture 8 (04-09-14) |
Voronoi diagram | - | (B1), (W1) |
| Lecture 9 (05-09-14) |
Duality | - | (B1), (W1) |
| Lecture 10 (09-10-14) |
Duality | - | (B1), (W1) |
| Lecture 11 (10-10-14) |
Duality; Closest pair |
- | (B1), (W1) |
| Lecture 12 (22-10-14) |
Halfplane intersection; Linear programming (Randomized Incremental Construction) Backward analysis |
- | (B1), (W1) |