Description
I) 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 NP-complete and APX-hard, and the best approximation ratio known is Omega(n^{-1/2}). Here we obtain better approximations in three special cases; for example, we obtain an Omega((\log{n})^{-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 Omega(n^2) vertices.
(II) We study variations of themes introduced/studied by
(a) Dudeney, (b) Erdős-Szekeres, (c) Erdős, Graham, Ruzsa, and Taylor,
(d) Gowers, (e) Payne-Wood, and (f) Zhang, from the combinatorial point of view. Given a set P of n points:
A. Find the largest general position subset, i.e., with no three collinear
B. Find the largest monotone general position subset
C. Find the largest subset with pairwise distinct slopes
Our results rely on probabilistic methods, results from incidence geometry, hypergraph containers, and additive combinatorics.
Part (II) is joint work with József Balogh, Felix Christian Clemen, and Dingyuan Liu.