On the General Position Subset Selection Problem
On the General Position Subset Selection Problem
Let $f(n,\ell)$ be the maximum integer such that every set of $n$ points in the plane with at most $\ell$ collinear contains a subset of $f(n,\ell)$ points with no three collinear. First we prove that if $\ell\leqslant O(\sqrt{n})$, then $f(n,\ell)\geqslant\Omega(\sqrt{n/\ln\ell})$. Second we prove that if $\ell\leqslant O(n^{(1-\epsilon)/2})$, then $f(n,\ell)\geqslant\Omega(\sqrt{n\log_\ell n})$, …