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 \le O(\sqrt{n})$ then $f(n,\ell )\ge \Omega (\sqrt{\frac{n}{\ln \ell }})$. Second we prove that if $\ell \le O(n^{(1-\epsilon )/2})$ then $f(n,\ell )\ge \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.

Cited by in corpus (7)

• Ramsey-type theorems for lines in 3-space
• Characterization of general position sets and its applications to cographs and bipartite graphs
• Graph theory general position problem
• On the general position set of two classes of graphs
• Convex Polygons in Cartesian Products
• The extensible No-Three-In-Line problem
• The Parameterized Complexity of Finding Point Sets with Hereditary Properties