On the General Position Subset Selection Problem

• Published in: SIAM journal on discrete mathematics 2013-01, Vol.27 (4), p.1727-1733
• Main Authors: Payne, Michael S., Wood, David R.
• Format: Article
• Language: English
• Subjects: Graphs
• ISSN: 0895-4801; 1095-7146
• DOI: 10.1137/120897493

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})$, which implies all previously known lower bounds on $f(n,\ell)$ and improves them when $\ell$ is not fixed. A more general problem is to consider subsets with at most $k$ collinear points in a point set with at most $\ell$ collinear. We also prove analogous results in this setting. [PUBLICATION ABSTRACT]