Skip to main content
3 of 3
Fixed link: Thanks to Julian Wilson
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

A type of generalization of the Erdős–Szekeres Theorem is that every set of at least $n= (m-3) \binom{k-1}{2} +k$ points in the plane contains either $m$ collinear points or $k$ points in general position. Specializing this to $k=m$ yields an expression in $O(m^3)$, matching your upper bound. Unfortunately I cannot access proofs at the moment, and so am uncertain if the bound is known to be tight. I have seen this result cited as in Peter Brass, "On point sets without $k$ collinear points," Discrete Geometry, 185-192, 2003; and in Zoltan Füredi, "Maximal independent subsets in Steiner systems and in planar sets," SIAM J. Discrete Math. 4(2), 196-199.

In any case, I think your question is a specialization of a generalization of the Erdős–Szekeres Theorem.

Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958