On Sets Defining Few Ordinary Lines

Abstract

Let $$P$$ be a set of $$n$$ points in the plane, not all on a line. We show that if $$n$$ is large then there are at least $$n/2$$ ordinary lines, that is to say lines passing through exactly two points of $$P$$ . This confirms, for large $$n$$ , a conjecture of Dirac and Motzkin. In fact we describe the exact extremisers for this problem, as well as all sets having fewer than $$n-C$$ ordinary lines for some absolute constant $$C$$ . We also solve, for large $$n$$ , the "orchard-planting problem", which asks for the maximum number of lines through exactly 3 points of $$P$$ . Underlying these results is a structure theorem which states that if $$P$$ has at most $$Kn$$ ordinary lines then all but O(K) points of $$P$$ lie on a cubic curve, if $$n$$ is sufficiently large depending on $$K$$ .

Locations

• Discrete & Computational Geometry - View - PDF
• Discrete & Computational Geometry - View - PDF