DIMACS Theoretical Computer Science Seminar

Title: Incidences between points and lines and extremal configuration of lines in Euclidean spaces.

Speaker: Noam Solomon, Tel Aviv University

Date: Wednesday, April 22, 2015 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ


In 1983, Szemeredi and Trotter proved a tight bound for the number of incidences between points and lines in the plane. Ever since then, incidence geometry has been a very active research area, bridging between computer science and mathematics, with many connections to diverse topics, from range searching algorithms to the Kakeya problem.

Over 25 years later, Guth and Katz proved a tight incidence bound for points and lines in three dimensions. Their proof introduced methods from advanced algebra and especially from algebraic geometry which were not used in combinatorics before. This enabled Guth and Katz to (almost) settle the Erdos distinct distances problem - a problem which stubbornly stood open for over 60 years, despite very brave attempts to solve it. The work of Guth and Katz has given significant added momentum to incidence geometry, making many problems, deemed hopeless before the breakthrough, amenable to the new techniques.

In this talk I will present the area of incidence geometry, before and after, highlighting the basics of the new ``algebraic'' approach, and will also present very recent results, joint with Micha Sharir, among which we studied incidences between points and lines in four dimensions, incidences between points and lines that lie on special surfaces and other related questions. We will also give a variety of interesting open related questions.

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S15/