2025/03/10 by Dumitrescu, Adrian
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2503.06857
Given a set of points in the 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 \rm NP-complete and \rm APX-hard, and the best approximation ratio known is Ω(\rm OPT-1/2) =Ω(n-1/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 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 generic n-line arrangement, i.e., one with Ω(n2) vertices. The scenario in (I) is a special case of that in (II). (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. Our approximations rely on probabilistic methods and results from incidence geometry.