In 1951, Gabriel Dirac conjectured that every non-collinear set P of n points in the plane contains a point incident to at least of the lines determined by P, for some constant c. The following weakened conjecture was proved by Beck and by Szemerédi and Trotter: every non-collinear set P of n points in the plane contains a point in at least lines determined by P, for some constant c0. We prove this result with We also give the best known constant for Beck's Theorem, proving that every set of n points with at most ' collinear determines at least lines.
|Number of pages||9|
|Journal||The Electronic Journal of Combinatorics|
|Publication status||Published - 16 Apr 2014|