| 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: Arijit Ghosh (ArG) and Arjit Bishnu (ArB) |
Class Timings: | Monday 14:15-16:00, Wednesday 14:15-16:00 ACMU seminar room (Platinum Jubilee Building) |
| The necessary evil - marks, exam, etc.: | Mid-sem: 10, End-sem: 50, Internal evaluation: 40 |
| 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) (20-01-20) |
Convex hull and ideas of Randomized Incremental Construction --
Read from Chapter 3 in (B5) or Chapter 9 in (B12)
Voronoi diagram --
Read the first subsection on Voronoi diagram in (B4) or from (W1) |
-- |
| Lecture 2 (ArB) (22-01-20) |
Delaunay triangulation --
Read the first two subsections on Delaunay triangulation from (B4)
Lifting transform: connecting convex hull with Delaunay triangulation --
Read from here or here |
-- |
| Lecture 3 (ArB) (27-01-20) |
Voronoi diagram and lifting transform --
Read from here or here or (W2)
Zone theorem --
Read from (B4) or (W2)
Polygon triangulation and Art Gallery Theorem --
Read from (B4) or (W2) |
-- |
| Lecture 4 (ArB) (29-01-20) |
Sylvester Gallai Theorem --
Read from (B8) or (W3)
Incidence problems, unit distance and distinct distance problem --
Read from (B1), (B2) or from (W3). |
-- |
| Lecture 5 (ArB) (03-02-20) |
Crossing lemma --
Read from (B1), (B8) or (W3)
Szemeredi Trotter theorem on point line incidences using crossing lemma --
Read from (B1) or (W3)
On sums and products (the paper by Elekes in Acta Arithmetica) --
Read the paper. |
-- |
| Lecture 6 (ArB) (05-02-20) |
Unit distance problem --
Read from (B1) or (W3)
Crossing lemma for multigraphs --
Read from (B1) |
-- |
| 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) |
-- |