On the General Position Subset Selection Problem

Abstract

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.

Locations

• SIAM Journal on Discrete Mathematics - View
• arXiv (Cornell University) - View - PDF
• CiteSeer X (The Pennsylvania State University) - View - PDF
• DataCite API - View