General Position Subset Selection in Line Arrangements

Given a set of points in the plane, the $\text{textsc}GeneralPositionSubsetSelection$ problem is that of finding a maximum-size subset of points in general position, i.e., with no three points collinear. The problem is known to be $\mathrm{N}\mathrm{P}$-complete and $\mathrm{A}\mathrm{P}\mathrm{X}$-hard, and the best approximation ratio known is $\mathrm{\Omega }\left({\mathrm{O}\mathrm{P}\mathrm{T}}^{-1\mathrm{/}2}\right)=\mathrm{\Omega }(n^{-1\mathrm{/}2})$. Here we obtain better approximations in three specials cases: (I) A constant factor approximation for the case where the input set consists of lattice points and is \emph{dense}, which means that the ratio between the maximum and the minimum distance in $P$ is of the order of $\mathrm{\Theta }(\sqrt{n})$. (II) An $\mathrm{\Omega }((\log n{)}^{-1\mathrm{/}2})$-approximation for the case where the input set is the set of vertices of a \emph{generic} $n$-line arrangement, i.e., one with $\mathrm{\Omega }(n^2)$ vertices. The scenario in (I) is a special case of that in (II). (III) An $\mathrm{\Omega }((\log n{)}^{-1\mathrm{/}2})$-approximation for the case where the input set has at most $O(\sqrt{n})$ points collinear and can be covered by $O(\sqrt{n})$ lines. Our approximations rely on probabilistic methods and results from incidence geometry.