Discrete Geometry, summer semester 2011

Contents of the lectures

• Tuesday, April 12, 2011
  • Algorithmic application examples: point pattern matching (repeated distances), clustering (halving lines)
  • k-sets and halving lines in the plane
  • the O(n^3/2) upper bound and the Ω(n log n) lower bound
• Tuesday, April 19, 2011
  • the crossing number theorem
  • the O(n^4/3) upper bound on halving sets
  • duality between points and lines
  • k-levels in arrangements
• Tuesday, April 26, 2011
  • the Ω(n⋅const^{√ log n}) lower bound on halving sets
  • parametric minimum spanning trees
• Tuesday, May 3, 2011
  • convex chains in line arrangements: crossings versus common tangents
  • the Szemerédi-Trotter bound on incidences between points and lines
  • unit circles and repeated distances
• Tuesday, May 10, 2011
  • 1/r-cuttings
• Tuesday, May 17, 2011
  • cuttings: probabilistic constructions
• Tuesday, May 31, 2011
  • Trapezoids intersecting many lines are rare
  • Clarkson's theorem on (≤k)-sets
  • The Clarkson-Shor random sampling technique
• Tuesday, June 7, 2011
  • ε-nets and ε-approximations
  • Vapnik-Chervonenkis dimension
  • the shatter function lemma
• Tuesday, June 21, 2011
  • the ε-net theorem
  • spanning trees with low crossing number
• Tuesday, June 28, 2011: no class
• Tuesday, July 5, 2011: guest lecture by Nabil Mustafa, lecture notes
  • weak ε-nets: history, open problems, proof of known results, various partial results.
• Tuesday, July 12, 2011
  • lower bounds for ε-nets