| Course Outline | General Information | Study Material | Lectures (classwise) |
The course consists of 4 lecture hours per week.
The basic thrust of the course would be to study combinatorics over geometric structures.
We will try to stick to the basic course outline as given in this page.
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.
| Taught by: Subhas C Nandy (SCN) and Arjit Bishnu (ArB) |
Class Timings: | Tuesday 14:15-16:00, Friday 16:15-18:00 ACMU seminar room (Platinum Jubilee Building) |
| The necessary evil - marks, exam, etc.: | Mid-sem: xx, End-sem: xx, Internal evaluation: xx |
| Books |
(B1) Lectures on Discrete Geometry Jiri Matousek Springer (B2) Combinatorial Geometry Janos Pach and Pankaj K Agarwal Wiley-Interscience (B3) Geometric and Topological Inference Jean-Daniel Boissonnat, F. Chazal and M. Yvinec Cambridge Texts in Applied Mathematics (B4) Computational Geometry: Algorithms and Applications Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars Springer Verlag (B5) Computational Geometry: An Introduction Through Randomized Algorithms Ketan Mulmuley Prentice Hall (B6) The Probabilistic Method Noga Alon, Joel H. Spencer 4th edition, Wiley (B7) Geometric Approximation Algorithms Sariel Har-Peled American Mathematical Society (B8) Proofs from THE BOOK Martin Aigner, Günter M. Ziegler Springer, 3rd edition (B9) Lectures on Discrete Geometry Jiri Matousek Springer (B10) Geometric Discrepancy Jiri Matousek Springer (B11) Davenport-Schinzel sequences and their applications Micha Sharir and Pankaj K Agarwal Cambridge University Press (B12) Randomized Algorithms Rajeev Motwani and Prabhakar Raghavan Cambridge |
| Web Resources |
(W1) Lecture Notes by Sariel Har Peled
(W2) Lecture Notes by David Mount (updated link) (W3) Lecture Notes by Torsten Ueckerdt (W4) Lecture Notes by Janos Pach |
| LECTURE DATES (Taught by) | TOPICS | EXERCISE |
| Lecture 1 (ArB) (15-02-22) |
Introductory examples, algorithms, convex polygon, etc. --
Read from any algorithms book |
-- |
| Lecture 2 (ArB) (18-02-22) |
Convex hull: Jarvis March, Graham's scan --
Read from (B4) and (W2) |
-- |
| Lecture 3 (ArB) (22-02-22) |
Lower bound: ideas and reduction, lower bound of convex hull, output sensitive convex hull --
Read from (B4) and (W2)
Zone theorem --
Read from (B4) or (W2)
Polygon triangulation and Art Gallery Theorem --
Read from (B4) or (W2) |
-- |
| Lecture 4 (ArB) (25-02-22) |
Higher dimensional convex hull -- conflict edge updating
Read from (xx) or (xx)
Voronoi diagrams: characterization, largest empty circle, bounds on the number of edges and faces, plane sweep algorithm --
Read from (xx), (xx) or from (xx). |
-- |
| Lecture 5 (ArB) (28-02-22) |
Delaunay triangulation: dual of Voronoi diagram --
Read from (xx), (xx) or (xx) |
-- |
| Lecture 6 (ArB) (01-03-22) |
-- | |
| Lecture 7 (ArB) (10-02-20) |
Crossing lemma for multigraphs --
Read from (B1)
Distinct distance problem --
Read from (B1) |
-- |
| Lecture 8 (ArB) (12-02-20) |
Notions of linear subspaces, linear combination, linear (in)dependence, linear span |
-- |
| Lecture 9 (ArB) (13-02-20) |
Convexity: Caratheodory's theorem for convex sets and positive cones; |
-- |
| Lecture 10 (ArB) (17-02-20) |
Farkas lemma; |
-- |
| Lecture 11 (ArB) (26-02-20) |
Helly's theorem; Centerpoint Theorem;
|
-- |
| Lecture 12 (ArB) (27-02-20) |
Hamsandwich cut in a linearly separable bichromatic point set using point line duality; |
-- |
| Lecture 13 (ArB) (12-03-20) |
Lower envelope and Davenport Schinzel sequences --
Read from (B1) and here.
Colorful Caratheodory theorem --
Read from (B1) |
-- |