General Position Subset Selection in Line Arrangements

Given a set of n points in a plane, the General Position Subset Selection 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 hard computationally, and the best approximation ratio known is Ω(n−1/2). Here, we obtain better approximations in three special cases: (I) a constant-factor approximation for the case where the input set consists of lattice points and is dense, which means that the ratio between the maximum and the minimum distance in P is of the order of Θ(n); (II) an Ω(logn)−1/2-approximation for the case where the input set is the set of vertices of a genericn-line arrangement, i.e., one with Ω(n2) vertices; and (III) an Ω(logn)−1/2-approximation for the case where the input set has at most O(n) points collinear and can be covered by O(n) lines. The scenario in (I) is a special case of that in (II). Our approximations rely on probabilistic methods and results from incidence geometry.