Skip to main content

Incidence Theorems and Their Applications

Author(s): Dvir, Zeev

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDvir, Zeev-
dc.identifier.citationDvir, Zeev. "Incidence Theorems and Their Applications." Foundations and Trends® in Theoretical Computer Science 6, no. 4 (2012): pp. 257-393. doi:10.1561/0400000056en_US
dc.description.abstractWe survey recent (and not so recent) results concerning arrangements of lines, points, and other geometric objects and the applications these results have in theoretical computer science and combinatorics. The three main types of problems we will discuss are: 1. Counting incidences: Given a set (or several sets) of geometric objects (lines, points, etc.), what is the maximum number of incidences (or intersections) that can exist between elements in different sets? We will see several results of this type, such as the Szemeredi–Trotter theorem, over the reals and over finite fields and discuss their applications in combinatorics (e.g., in the recent solution of Guth and Katz to Erdos' distance problem) and in computer science (in explicit constructions of multisource extractors). 2. Kakeya type problems: These problems deal with arrangements of lines that point in different directions. The goal is to try and understand to what extent these lines can overlap one another. We will discuss these questions both over the reals and over finite fields and see how they come up in the theory of randomness extractors. 3. Sylvester–Gallai type problems: In this type of problems, one is presented with a configuration of points that contain many 'local' dependencies (e.g., three points on a line) and is asked to derive a bound on the dimension of the span of all points. We will discuss several recent results of this type, over various fields, and see their connection to the theory of locally correctable error-correcting codes. Throughout the different parts of the survey, two types of techniques will make frequent appearance. One is the polynomial method, which uses polynomial interpolation to impose an algebraic structure on the problem at hand. The other recurrent techniques will come from the area of additive combinatorics.en_US
dc.format.extent257 - 393en_US
dc.relation.ispartofFoundations and Trends® in Theoretical Computer Scienceen_US
dc.rightsAuthor's manuscripten_US
dc.titleIncidence Theorems and Their Applicationsen_US
dc.typeJournal Articleen_US

Files in This Item:
File Description SizeFormat 
IncidenceTheoremsTheirApplications.pdf698.74 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.