A type of generalization of the [Erdős–Szekeres Theorem][1] 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][2]," _Discrete Geometry_, 185-192, 2003; and in Zoltan Füredi, "[Maximal independent subsets in Steiner systems and in planar sets][3]," _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. [1]: http://en.wikipedia.org/wiki/Erdos-Szekeres_theorem [2]: http://www.crcnetbase.com/doi/abs/10.1201/9780203911211.ch12 [3]: http://portal.acm.org/citation.cfm?id=105818