Incidence Geometry and Its Applications (Summer students programme, 2018)
Instructor Arijit Ghosh
Description A brief introduction to Incidence Geometry.
Intended Audience TCS summer students at IMSC.
References
[KMS12] Kaplan, Matousek and Sharir, Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique, Discrete & Computational Geometry, 48 (3): 499–517, 2012.
[D12] Z. Dvir, Incidence Theorems and Their Applications, Foundations and Trends in Theoretical Computer Science, 2012.
[LR] Landau-Ramanujan Constant.
[I08] A. Iosevich, Fourier Analysis and Geometric Combinatorics, Topics in Mathematical Analysis, pages 321-335, 2008.
Lecture details
Topics covered in Lecture 1
Statements of Szemeredi-Trotter (ST) theorem and Pach-Sharir's refinement of ST Theorem.
Applications of ST:
Bounding the number of heavy lines.
Beck's Ramsey-type result for points and lines in 2D.
Elekes's Sum-Product estimate using ST.
Erdos's Unit Distance estimate using ST.
Lower bound on Erdos's distinct distance problem using Landau-Ramanujan Constant [LR].
Reading materials:
Topics covered in Lecture 2
Number of lattice points on a Convex Curve in 2D via ST theorem.
Statement of Guth-Katz's Polynomial Partitioning Theorem.
Existence of low degree of polynomials vanishing on a finite set in d-dimensional Euclidean space.
Statement of Ham-Sandwich Theorem.
Statement and Proof of Polynomial Ham-Sandwich Theorem.
Simple properties of polynomials.
Reading materials:
Topics covered in Lecture 3
Proof of ST Theorem using Polynomial Partitioning Theorem.
Proof of Polynomial Partitioning Theorem using Polynomial Ham-Sandwich Theorem.
Reading materials:
Topics covered in Lecture 4