E0 318: Topics in Geometric Algorithms, Fall 2024

Instructors: Siddharth Barman and Arindam Khan

Time: Tue-Thu, 14:00-15:30, CSA117.

Course Description

Geometric problems are ubiquitous in Computer Science (see Geometry Applications) -- from graphics and visualization to VLSI design; from motion planning in robotics to geometric packing in logistics. One also encounters geometric problems and associated algorithms in data science applications; examples include clustering problems in unsupervised learning, nearest neighbor search, and hashing methods that exploit the geometry of input points. In addition to critical applications, geometric algorithms connect with mathematical fields such as probability theory, combinatorics, and topology. This course will cover algorithmic approaches for addressing topical problems in computational geometry. Further, by way of course projects, we will identify and explore some key open problems in such topics.

Tentative topics:
High Dimensinal Geometry (applications in ML and Data Science):
Epsilon Nets and VC Dimensions, Coresets, Clustering, LSH and Approximate Nearest Neighbor, Learning-Augmented Algorithms, JL Lemma and dimensionality reduction, Approximating Convex Body.
Misc. Geometric Techniques: Polynomial methods in Geometry, Sampling, Geometric Separators, Approximation Schemes (Euclidean TSP: Quadtrees, Portals, Guillotine Cuts).

Twenty-Five Open Problems in Geometric Algorithms

Open problems proposed during the workshop on Frontiers of Geometric Algorithms in December 2024 at IISc.

Lectures

• Probability Refresher: Scribe notes from Toolkit, Handwritten notes.
  Useful inequalities: Cheatsheet.
  


• Week 1:
  VC dimensions and Epsilon Net:
  VC Dimension, Epsilon Net, Epsilon Sample, PAC and Agnostic Learning.
  Applications in Set Cover and Art Gallery Problem.
  [MU Chapter 14 and HP Chapter 6]
  Handwritten Notes.
  Video Lectures by Arindam Khan: [from other courses] VC-dimension, Shattering dimension, eps-net, PAC Learning, VC Dimension and Applications in Set Cover, Hitting Set, and Art Gallery Problem.
  Related Links:
  VC dimension and ML [by Erik Xing], VC dimension and ML [by Miao Liao].


• Week 2:
  Coresets, Clustering:
  Coresets, Epsilon-kernel: Grid-based and Nearest Neighbor Algorithms;
  Clustering: Generalized k-center, Greedy 2-approximation, Additive and Multiplicative Coresets for Clustering.
  [Survey by Agarwal, Har-Peled, Varadarajan; and Chapter 23 from HP.]
  Handwritten Notes.
  Notes by Dave Mount.
  Video: Introduction to Coresets (FoGA Workshop at IISc) by Chris Schwiegelshohn.


• Week 3:
  Approximate Nearest Neighbor via Point-Location
[Chapter 18 From HP].
Videos by Aditya Subramanian: part 1, part 2, part 3. Handwritten Notes.


• Week 4:
  Approximate Nearest Neighbor in Higher Dimensions: LSH
[Chapter 20 From HP].
Videos by KVN Sreenivas , Handwritten Notes.
Talk by Piotr Indyk (ICM 2018) .
Talk by Ankur Moitra .
Beyond Locality-Sensitive Hashing: Talk by Alex Andoni.
Talk by Jeff Ullman: part 1, part 2.


• Week 5: Polynomial Methods in Geometry:
  Combinatorial Nullstellensatz, Polynomials vanishing at a point and Polynomial partitioning.
  Applications: Alon-Furedi results on almost covering the hypercube, finite field Kakeya Conjecture, Lines and joints problem in 3D, Szemeredi-Trotter Theorem bounding incidences between points and lines in plane.
Videos by Soumi Nandi: part 1, part 2, part 3. Handwritten Notes.
Applications -- ε-Kernel and Approximate Nearest Neighbor: SoCG'17 paper by Timothy Chan.
Related Links:
Videos by Larry Guth. Slides by Larry Guth. Book by Larry Guth.


• Week 6-7: Johnson–Lindenstrauss lemma and High Dimensional Probability.
  Matrix Deviation Inequality and its geometric applications.
[Chapter 21-22 From HP].
Talk on JL Lemma by Mary Wooters (Stanford).
Lecture on JL Lemma and Extensions by Ankur Moitra (MIT) .
Tug-of-War sketches and JL (Talk by Thatchaphol (UMich)).
Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation (Talk by Erik Waingarten (UPenn)).


• Week 8: Approximating convex body/min volume bounding box.
[Chapter 21-22 From HP].
John's Theorem and Optimal Design: Videos by Nirjhar Das. Scribe.


• Week 9-10: Learning Augmented Algorithms in Geometry.
Lectures by Akash Pareek:
Introduction to Learning-Augmented Algorithms: Video, Notes, Book chapter on Algorithms with Predictions.
Learning-Augmented k-means: Video, Notes, Paper.
Improved Learning-Augmented Algorithm for k-means: Video, Notes, Paper.
Online TSP with predictions: Scribe by Rahul Adhikari, Handwritten Notes, Online TSP paper, TSP with predictions paper.
Related Links:
Resources on Algorithms with Predictions.
Recent TTIC workshop and videos.


• Week 11: Depth Estimation via Sampling.
[Chapter 9-10 From HP].
Videos by Nikhilesh Rajaraman. Slides.


• Week 12: Euclidean TSP.
[Chapter 13-14 From HP].
Scribe by Abhiram.
Euclidean TSP -- PTAS by Sanjeev Arora, by Joe Mitchell.
Recent Advanced Results: TSP with Neighbourhoods [Dumitrescu-Mitchell], TSP with Hyperplane Neighbourhoods [Antoniadis et al.], Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP [Moemke-Zhou].
Video: Tight results on Euclidean TSP (FoGA Workshop at IISc) by Tobias Moemke.


• Week 13: Geometric Separators.
Book Chapter by Sariel Har-Peled.
Lipton-Tarjan Planar Separator Paper.
Beyond Planarity: On Geometric Intersection Graphs (videos by Sariel Har-Peled): The circle packing theorem, The planar separator theorem, Low-density and polynomial expansion graphs, Local search and approximation algorithms, Hardness, thesis and open problems.
Video: Introduction to Geometric Separators at FoGA Workshop at IISc and NYU CG Seminar by Mark deBerg.
Advanced Topics: String Graphs (Fox-Pach), MISR (Adamaszek-HarPeled-Wiese), Clique-based Separators.

References

We will be teaching materials from multiple books/sources. Some of them are the following.
• [HP] Sariel Har-Peled, Geometric Approximation Algorithms. American Mathematical Soc., 2011.
• [MMM] Mark DB, Otfried C, Marc VK, Mark O. Computational geometry algorithms and applications. Springer; 2008.
• [MU] Michael Mitzenmacher and Eli Upfal. Probability and computing. Cambridge university press, 2017.
• [RV] Roman Vershynin, High-Dimensional Probability.
• [BHK] Blum, Hopcroft, and Kannan. Foundations of Data Science.
• [WS] Williamson, David P., and David B. Shmoys. The design of approximation algorithms. Cambridge University Press, 2011.
• [BJB] Barbanel, Julius B. The geometry of efficient fair division. Cambridge University Press, 2005.
• [TR] TimRoughgarden. Beyond the Worst-Case Analysis.
• Various surveys and lecture notes. (e.g., https://graphics.stanford.edu/courses/cs468-06-fall/)



---

Useful Webpages

• Computational Geometry Pages, a comprehensive directory of computational geometry resources: Books,
• Frontiers of Geometric Algorithms, an international workshop at IISc during December 11-15.
• Geometric Approximation Algorithms (UIUC), by Timothy Chan.
• Approximation Algorithms (IISc), by Arindam Khan and Anand Louis.
• Introduction to Randomized Algorithms (IISc), by Arindam Khan and Jaikumar Radhakrishnan.
• Algorithms under Uncertainty (IISc), by Siddharth Barman and Arindam Khan.
• Theorists Toolkit (IISc), by Arindam Khan and Anand Louis.
• Algorithms text book, by Jeff Erickson.
• Geometry in action, by David Eppstein.
• CG: SHOP (programming competition), Computational Geometry: Solving Hard Optimization Problems.



---

Mathematical writing and LaTeX

• How to write mathematics (Halmos)
• Mathematical writing (Knuth et al.)
• Scribe template: preamble.tex, lect01.tex
• Overleaf: Learn LaTex
• MIT: Intro to LaTex
• Evan Chen's LaTex hacks
• TikZ package for drawing




---

Intended audience: Graduate students in computer science and mathematics with research interests in algorithms, specially in computational geometry and approximation algorithms.

Prerequisites: Students should have completed E0 225 (Design and Analysis of Algorithms) and Computational Geometry (E0 208) or Approximation Algorithms (E0 249).

Grading: 30% Presentations, 40% Report, 30% Scribe+Class Participation.

---

Prepared and Maintained by Arindam Khan

---