Subset Selection Problems in Planar Point Sets


                      Adrian Dumitrescu
               Algoresearch L.L.C., Milwaukee, WI         

(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 specials cases; for example, we obtain a 
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\H{o}s-Szekeres, (c) Erd\H{o}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 a largest general position subset, i.e., with no three collinear
     B. Find a largest monotone general position subset
     C. Find a 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\'ozsef Balogh, Felix Christian Clemen, and Dingyuan Liu